Compact Representation of Semilinear and Terrain-like Graphs
Jean Cardinal, Yelena Yuditsky · 2025
Read Compact Representation of Semilinear and Terrain-like Graphs by Jean Cardinal, Yelena Yuditsky (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-00252.txt.
Introduction
Jean Cardinal and Yelena Yuditsky survey and extend a way to store graphs in a compact form. A graph can be covered by complete two-sided blocks, where each block joins two groups in full. The total size of such a cover sets how small the stored form can be. Small covers pop up across geometry work and serve as neat graph codes. Their paper sums old results and adds fresh graph families with near-linear cover size.
One new family is graphs whose edges come from linear rules in bounded space, a broad class. That one result re-proves bounds for many known classes, from interval graphs to shape-crossing graphs. A second family, graphs that shun one small ordered pattern, also gets a near-linear cover by a plain proof. Shapes from land view graphs sit in that second class.
Catalog record
| CREATOR | Jean Cardinal, Yelena Yuditsky |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 62 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-00252
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Compact Representation of Semilinear and Terrain-like Graphs Jean Cardinal, Yelena Yuditsky Abstract . We consider the existence and construction of biclique covers of graphs, consisting of coverings of their edge sets by complete bipartite graphs. The size of such a cover is the sum of the sizes of the bicliques. Small-size biclique covers of graphs are ubiquitous in computational geometry, and have been shown to be useful compact representations of graphs. We give a brief survey of classical and recent results on biclique covers and their applications, and give new families of graphs having biclique covers of near-linear size. In particular, we show that semilinear graphs, whose edges are defined by linear relations in bounded dimensional space, always have biclique covers of size O ( n polylog n ) O(n\polylog n) . This generalizes many previously known results on special classes of graphs including interval graphs, permutation graphs, and graphs of bounded boxicity, but also new classes such as intersection graphs of L-shapes in the plane. It also directly implies the bounds for Zarankiewicz’s problem derived by Basit, Chernikov, Starchenko, Tao, and Tran ( Forum Math. Sigma , 2021). We also consider capped graphs, also known as terrain-like graphs, defined as ordered graphs forbidding a certain ordered pattern on four vertices. Terrain-like graphs contain the induced subgraphs of terrain visibility graphs. We give an elementary proof that these graphs admit biclique partitions of size O ( n log 3 n ) O(n\log^{3}n) . This provides a simple combinatorial analogue of a classical result from Agarwal, Alon, Aronov, and Suri on polygon visibility graphs ( Discrete Comput. Geom. 1994). Finally, we prove that there exists families of unit disk graphs on n n vertices that do not admit biclique coverings of size o ( n 4 / 3 ) o(n^{4/3}) , showing that we are unlikely to improve on Szemerédi-Trotter type incidence bounds for higher-degree semialgebraic graphs. 1. Introduction Graph covering and partitioning is a well-studied topic in graph theory with numerous connections to real-world problems, see for example the survey of Schwartz [ 74 ] . Given a graph G , a cover of G is a collection \mathcal{H} of subgraphs of G such that each edge of G is contained in at least one of the subgraphs in \mathcal{H} , that is, E(G)\subseteq\bigcup_{H\in\mathcal{H}}E(H) . A partition of G is a collection \mathcal{H} of subgraphs of G such that each edge of G is contained in exactly one of the subgraphs in \mathcal{H} . Clearly, any partition of a graph is also a cover. The subgraphs in the cover (or partition) can be chosen in different ways, for example, they can be chosen to be cliques, complete bipartite graphs (to which we refer as bicliques ), cycles, paths, and other graphs (see [ 74 ] for a list of results for each of those graph classes). A natural problem is, for a given graph, to determine the smallest possible number of subgraphs in a cover. We are interested in a related parameter of the cover. Let G be a graph and let \mathcal{H} be a cover of G with any type of subgraphs. The size of a cover \mathcal{H} is \sum_{H\in\mathcal{H}}|V(H)| . Clearly, those parameters are related. If G has a cover with \ell subgraphs, then there is also a cover of G of size \ell n where n=|V(G)| . In this work, we focus on the size of covers with bicliques, to which we refer as biclique covers . See Figure 1 for an example of biclique cover of a graph. Figure 1 . An example of a graph and a biclique cover with three bicliques of total size 15 . Biclique covers have applications to the multicommodity flow problem [ 51 ] , quantified Boolean formulas [ 61 ] , and communication complexity of boolean functions [ 57 ] . In a seminal paper, Feder and Motwani [ 45 ] showed that biclique covers of small sizes can be used as compact representations of graphs, on which many computational problems can be solved more efficiently than on standard representations. The minimum size of a biclique cover of a graph is therefore sometimes referred to as its representation complexity [ 41 ] . 1.1. Our results We study biclique covers for various classes of graphs defined in geometric terms. We focus on graph classes for which there exist biclique covers of size O(n\polylog n) , where n is the number of vertices. Some of the terms used below are defined in the next section 1.2 . Our contribution is threefold. We first consider semilinear graphs , defined as semialgebraic graphs for which the defining functions are linear. This class of graphs has first been defined by Basit, Chernikov, Starchenko, Tao, and Tran [ 14 ] , and further studied by Tomon [ 79 ] . We generalize a number of results above by showing that semilinear graphs have biclique partitions of size O(n\polylog n) . This in particular gives a simple proof of the bound on Zarankiewicz’s problem for semilinear graphs shown by Basit et al. [ 14 ] . Semilinear graphs include many previously studied graph classes such as interval graphs, threshold graphs, permutation graphs, bounded-dimension comparability graphs, bounded-boxicity graphs, and intersection graphs of L -shapes and other orthogonal shapes in the plane. For certain restricted classes of semilinear graphs, we establish improved bounds on the size of a biclique cover compared to those obtainable from the general bounds. We then show that terrain-like graphs , also known as capped graphs [ 38 ] have biclique partitions of size O(n\log^{3}n) . These graphs contain in particular induced subgraphs of terrain visibility graphs . This result can be seen as a combinatorial variant of the influential result of Agarwal, Alon, Aronov, and Sharir [ 3 ] on compact representation of visibility graphs of polygons, since terrain-like graphs include terrain visibility graphs. The two results, however, are incomparable, since there exist terrain-like graphs that are not visibility graphs of terrains [ 12 ] . Finally, we answer a question asked by Csaba Tóth [ 81 ] : Can unit disk graphs have near-linear biclique covers? Note that the existence of such covers is not ruled out by a counting argument, since there are 2^{O(n\log n)} unit disk graphs on n vertices [ 73 ] . Yet, we answer the question in the negative: There exist unit disk graphs on n vertices, every biclique cover of which has size \Omega(n^{4/3}) , which is essentially tight. This is proved by considering the standard examples of configurations of points and lines that are tight for the Szemerédi-Trotter Theorem [ 69 ] , and applying a charging argument. Together with our upper bound for semilinear graphs, this result provides a delineation of what classes of graphs have near-linear biclique covers; as soon as we allow the functions defining a semialgebraic graph to be of degree two, we may obtain strongly superlinear lower bounds on the size of biclique covers. 1.2. Background Before detailing our results, we first give a brief survey of known results and applications of biclique covers and partitions. We take the opportunity here to