Compact Representation of Semilinear and Terrain-Like Graphs

Cardinal, Jean; Yuditsky, Yelena

doi:10.4230/LIPIcs.ESA.2025.67

Compact Representation of Semilinear and Terrain-Like Graphs

Jean Cardinal

Université libre de Bruxelles (ULB), Belgium Yelena Yuditsky

Université libre de Bruxelles (ULB), Belgium

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\operatorname{\mathrm{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)$ . 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$ vertices that do not admit biclique coverings of size $o(n^{4/3})$ , showing that we are unlikely to improve on Szemerédi-Trotter type incidence bounds for higher-degree semialgebraic graphs.

Keywords and phrases:

Biclique covers, intersection graphs, visibility graphs, Zarankiewicz’s problem

Funding:

Jean Cardinal: Jean Cardinal was supported by the Fonds de la Recherche Scientifique - FNRS under Grant n° T003325F.

Yelena Yuditsky: Yelena Yuditsky was supported by the Fonds de la Recherche Scientifique - FNRS as a Postdoctoral Researcher.

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Computational geometry ; Theory of computation

\rightarrow

Graph algorithms analysis

Related Version:

Full Version: https://arxiv.org/abs/2507.00252 [20]

Acknowledgements:

This work was inspired by discussions at the Tenth Annual Workshop on Geometry and Graphs (WoGaG’23), held at the Bellairs Research Institute, (McGill), Barbados, in February 2023.

DOI:

10.4230/LIPIcs.ESA.2025.67

Event:

33rd Annual European Symposium on Algorithms (ESA 2025)

Editors:

Anne Benoit, Haim Kaplan, Sebastian Wild, and Grzegorz Herman

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

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 [68]. 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 [68] 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 [47], quantified Boolean formulas [55], and communication complexity of boolean functions [51]. In a seminal paper, Feder and Motwani [41] 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 [37].

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\operatorname{\mathrm{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 [13], and further studied by Tomon [73]. We generalize a number of results above by showing that semilinear graphs have biclique partitions of size $O(n\operatorname{\mathrm{polylog}}n)$ . This in particular gives a simple proof of the bound on Zarankiewicz’s problem for semilinear graphs shown by Basit et al. [13]. 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 [34] 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 [11].

Finally, we answer a question asked by Csaba Tóth [74]: 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 [67]. 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 [63], 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 gather results that are sometimes considered as folklore, but were never thoroughly compiled.

1.2.1 Covers and partitions in general graphs

The minimal number of bicliques needed to cover a graph has been studied by Tuza [75], Rödl and Ruciński [66], and Jukna and Kulikov [51], among others. As mentioned earlier, we are interested in the size of a biclique cover, which, to recall, is defined as the sum of the number of vertices across all the bicliques in the cover. Let us first note that if $G$ is an $n$ -vertex graph with $O(n)$ edges, then $G$ has a trivial biclique cover of size $O(n)$ . Hence the question of bounding the size of a biclique cover is not relevant in classes of graphs with linearly many edges, such as bounded-treewidth graphs or planar graphs.

A cover of size $O(n\log n)$ of the complete graph $K_{n}$ can be obtained recursively as follows: first split the set of vertices into two disjoint subsets of equal size, and add the corresponding biclique to the cover, then recurse on both subsets. The cover we obtain in this way is also a biclique partition with $n$ bicliques.

A bound on the size of a biclique cover of an arbitrary graph was proved by Chung, Erdős, and Spencer [30], and later by Tuza [75].

Theorem 1 ([30, 75]).

Let $G$ be a graph on $n$ vertices. Then there exists a biclique cover of $G$ of size $O(n^{2}/\log n)$ , and this bound is tight.

We observe a connection between the size of a biclique cover and constructions of graphs with many edges and without a complete bipartite graph $K_{t,t}$ as a subgraph, also known as the Zarankiewicz problem. We refer, for example, to Conlon [31] for a construction of such graphs and to Smorodinsky [70] for a survey on the Zarankiewicz problem in geometric graphs. Let $G$ be a graph without a $K_{t,t}$ subgraph and let $\mathcal{H}$ be a biclique cover of $G$ . Let $H\in\mathcal{H}$ , then $|E(H)|\leq t|V(H)|$ and therefore $\sum_{H\in\mathcal{H}}|V(H)|\geq\sum_{H\in\mathcal{H}}|E(H)|/t\geq|E(G)|/t$ . Hence we can deduce the following observation.

Observation 2.

Let $G$ be a graph without a $K_{t,t}$ subgraph, for some $t\in\mathbb{N}$ , and with a biclique cover of size $s$ . Then $G$ has at most $t\cdot s$ edges.

For classes of graphs that have biclique partition of size $O(n\operatorname{\mathrm{polylog}}n)$ , like the ones studied in this paper, this directly gives an upper bound of $O(n\operatorname{\mathrm{polylog}}n)$ on the number of edges of these graphs when $K_{t,t}$ is forbidden, for some constant $t$ .

Let $\mathcal{F}$ be a class of graphs and let $\mathcal{F}_{n}$ be the graphs in $\mathcal{F}$ with exactly $n$ vertices. If any graph $G\in\mathcal{F}_{n}$ has a biclique cover of size $s(n)$ then $|\mathcal{F}_{n}|\leq 2^{s(n)\lceil\log n\rceil+2s(n)}$ . Indeed, every graph can be encoded by a binary string of length at most $s(n)\lceil\log n\rceil+2s(n)$ where every vertex is encoded by a binary string of length $\lceil\log n\rceil$ and at most $2s(n)$ additional bits separating the bicliques and defining the bipartition inside each biclique. Based on the above, we make the following observation.

Observation 3.

Let $\mathcal{F}$ be a family of graphs and let $s(n)$ be the maximum size of a biclique cover of a graph in $\mathcal{F}_{n}$ , then $|\mathcal{F}_{n}|\leq 2^{O(s(n)\log n)}$ .

Note that for many classes of geometric graphs, the upper bound in the above observation is significantly worse than the best known upper bounds [67].

1.2.2 Algorithms

Feder and Motwani [41] observed that biclique covers can be used to construct compressed representations of graphs, on which several computational problems can be solved efficiently. In a compressed representation, each biclique in the cover is replaced by a subgraph whose number of edges is proportional to the size of the biclique. This can be interpreted as a sparsification procedure, that preserves features of the initial graph while reducing the number of edges. A simple application of this idea is to the all-pairs shortest paths problem.

Lemma 4 ([41]).

Given a biclique cover of size $s$ of a graph $G$ on $n$ vertices, then the breadth-first search tree rooted at any vertex of $G$ can be computed in time $O(s)$ , hence the (unweighted) all-pairs shortest paths problem can be solved in time $O(n\cdot s)$ .

We refer to Chan and Skrepetos [25] for a discussion on the application of this result to geometric intersection graphs.

Similarly, Feder and Motwani proved that a maximum matching of a bipartite graph given in compressed form as a biclique cover of size $s$ can be found in time $O(\sqrt{n}\cdot s)$ [41, Theorem 4.2]. Using a state-of-the-art maximum flow algorithm [29, 76], Cabello, Cheng, Cheong, and Knauer [18] gave the following improvement.

Lemma 5 ([18]).

Given a biclique cover of size $s$ of a bipartite graph $G$ , the maximum matching problem on $G$ can be solved in time $O(s^{1+\varepsilon})$ for any $\varepsilon>0$ .

Note that in these results, we assume that a biclique cover is given, and do not take into account the time required to compute it. Ideally, if the graph is given in some kind of implicit form (for instance as a collection of geometric object, of which the graph is the intersection graph), we may hope to be able to compute the biclique cover in time proportional to its size, and then apply the above lemmas.

1.2.3 Spanners

Let $t\in\mathbb{N}$ and let $G$ be a graph. A $t$ -hop spanner is a subgraph $G^{\prime}$ of $G$ such that for any $uv\in E(G)$ , there is a path of length at most $t$ in $G^{\prime}$ between $u$ and $v$ . The following was observed by Conroy and Tóth [33].

Lemma 6 ([33]).

If $G$ has a biclique cover of size $s$ then there is a subgraph $G^{\prime}$ of $G$ which is a $3$ -hop spanner with $s$ edges.

This is achieved by simply replacing every biclique of the decomposition by two stars, with centers on either side of the bipartition.

Biclique covers of intersection graphs of boxes in constant dimension are also used in a recent preprint by Bhore, Chan, Huang, Smorodinsky and Tóth [14] to obtain $2$ -hop spanners for fat axis-aligned boxes.

1.2.4 Biclique covers and range searching

Biclique covers and partitions of geometric graphs are natural byproducts of range searching algorithms and data structures in computational geometry. The range searching problem can be defined as that of preprocessing a collection of points in $\mathbb{R}^{d}$ so as to quickly answer queries about the subset of points contained in a given region, called the range. There, bicliques naturally arise as pairs of subsets of points and ranges, such that all points are contained in all ranges. Classical data structures for orthogonal range searching, where ranges are axis-aligned boxes, include segment trees and range trees [35, Chapters 5 and 10]. Halfspace and simplex range queries are typically answered using cuttings and partition trees [58, 59, 26, 60, 23]. More recently, polynomial partitioning techniques, stemming from the seminal paper from Guth and Katz [48], have been used to solve semialgebraic range queries [61, 37, 4, 19, 7]. These structures naturally yield biclique covers of the corresponding incidence graphs. In turn, running times for the offline range searching problem are closely related to incidence bounds [63], an early example of which is the Szemerédi-Trotter theorem bounding the number of incidences between points and lines in the plane. Quoting Agarwal, Ezra, and Sharir [7]: “there is a general belief that the two problems are closely related, and that the running time of (at least off-line) range queries should be almost the same as the number of incidences between points and the corresponding curves/surfaces that bound these regions”. It is therefore not surprising that incidence bounds often coincide with representation complexities.

We summarize the known upper bounds stemming from this line of work. Let $P$ be a set of points and let $R$ be a set of geometric objects in $\mathbb{R}^{d}$ . An incidence graph $I(P,R)$ is a bipartite graph with the bipartition $(P,R)$ where there is an edge between two elements $p\in P$ and $r\in R$ if and only if $p\in r$ . We henceforth assume that every set of points or geometric objects contains at most $n$ elements. The following results are known (the $\tilde{O}$ notation omits polylogarithmic factors):

$\blacksquare$

Incidence graphs of points and axis-parallel boxes in $\mathbb{R}^{d}$ , for some constant $d$ , have biclique partitions of size $O(n\log^{d}n)$ . This can be deduced from [6, Section 3] and [35, Chapter 5], for instance.
$\blacksquare$

Incidence graphs of points and halfspaces in $\mathbb{R}^{d}$ , for some constant $d$ , have biclique partitions of size $\tilde{O}(n^{2d/(d+1)})$ [57].
$\blacksquare$

Incidence graphs of points and hyperplanes in $\mathbb{R}^{d}$ , for some constant $d$ , have biclique partitions of size $\tilde{O}(n^{2d/(d+1)})$ [17].
$\blacksquare$

Incidence graphs of points and unit disks have biclique partitions of size $\tilde{O}(n^{4/3})$ [54].
$\blacksquare$

Incidence graphs of points and disks (of arbitrary radii) have biclique partitions of size $\tilde{O}(n^{15/11})$ [7].

In all these cases, the biclique covers can be constructed in time proportional to their size.

Results by Erickson [39] on Hopcroft’s problem make the connection between range searching problems and biclique covers explicit. It is shown, among other results, that the running time of a type of a partitioning algorithm for the counting version of Hopcroft’s problem with respect to a set of points $P$ and hyperplanes $H$ is bounded from below by the size of the biclique cover of $I(P,H)$ .

Biclique covers also have other applications in computational geometry. For instance Agarwal and Varadarajan [8] use them to compute approximations of polygonal chains, and biclique partitions of pairs of points at bounded distance from each other are also at the heart of the expander-based optimization method proposed by Katz and Sharir [54].

A graph $G$ is an intersection graph for a class of geometric objects if its vertices can be mapped to objects in the class so that two vertices are adjacent if and only if the corresponding objects have a nonempty intersection. As mentioned by Agarwal et al. [7], interval graphs, intersection graph of intervals on the real line, have biclique partitions of size $O(n\log n)$ . More generally, it was shown by Chan [21] that intersection graphs of axis-aligned boxes in $\mathbb{R}^{d}$ have a biclique cover of size $O(n\log^{d}n)$ . The boxicity of a graph $G$ is the minimum $d$ such that $G$ is an intersection graph of axis-aligned boxes in $\mathbb{R}^{d}$ . Hence this result shows that bounded-boxicity graphs have near-linear size biclique covers. For intersection graphs of unit disks in the plane, a bound of $\tilde{O}(n^{4/3})$ on the size of a biclique cover can be derived from the bound on the size of a biclique cover in the incidence graph between a set of points and unit disks in the plane. Segment intersection graphs have biclique covers of size $\tilde{O}(n^{4/3})$ [8, 7]. Finally, Chazelle, Edelsbrunner, Guibas, and Sharir [27] proved that the bipartite intersection graph between a set of $n$ disjoint blue segments and a set of $n$ disjoint red segments in the plane has a biclique cover of size $O(n\log^{3}n)$ .¹¹1The result is not explicitly stated, but can be deduced from their method for reporting intersections, involving so-called hereditary segment trees. See the full version of the paper [20] for details. See also Palazzi and Snoeyink [64].

Many natural classes of geometric graphs are contained in the class of semialgebraic graphs [10, 32, 42, 71]. A graph $G=(V,E)$ is a semialgebraic graph of description complexity $t$ and dimension $d$ if the vertices in $V$ can be mapped to points in $\mathbb{R}^{d}$ so that the presence of an edge is defined by the sign patterns of $t$ polynomial functions of the corresponding pair of points. More precisely, there must exist:

$\blacksquare$

a map $\varphi:V\mapsto\mathbb{R}^{d}$ ,
$\blacksquare$

$t$ polynomials $f_{1},\ldots,f_{t}\in\mathbb{R}[x_{1},\ldots,x_{d},y_{1},\ldots y_{d}]$ each of degree at most $t$ in $2d$ variables,
$\blacksquare$

a boolean function $\Phi:\{\text{T},\text{F}\}^{3t}\rightarrow\{\text{T},\text{F}\}$ ,

such that for any $u,v\in V$ ,

uv\in E\Leftrightarrow\Phi\left(\{f_{i}(\varphi(u),\varphi(v))<0,f_{i}(\varphi% (u),\varphi(v))=0,f_{i}(\varphi(u),\varphi(v))\leq 0\}_{i\in[t]}\right)=T.

For example, two closed disks of center respectively $(a,b)$ and $(c,d)$ and radius $r$ and $s$ , for instance, have a nonempty intersection if and only if $f(a,b,r,c,d,s)\leq 0$ , where $f(a,b,r,c,d,s)=(a-c)^{2}+(b-d)^{2}-(r+s)^{2}$ . Hence disk intersection graphs are semialgebraic graphs of dimension $d=3$ . Note that the union of constantly many semialgebraic graphs is also a semialgebraic graph.

The following result has been proved by Do [37]. A computationally efficient version can be found in Agarwal, Aronov, Ezra, Katz, and Sharir [5, Corollary A.5].

Theorem 7 ([37, 5]).

Let $G$ be a semialgebraic graph on $n$ vertices of constant description complexity $t$ and constant dimension $d$ . Then for any $\varepsilon>0$ , $G$ has a biclique cover of size $O(n^{2d/(d+1)+\varepsilon})$ , where the constants in the $O$ depend on $\varepsilon$ , $t$ , and $d$ .

Chan, Cheng, and Zheng [24, Final Remarks] showed that the intersection graph of $n$ algebraic arcs in the plane of constant description complexity has a biclique cover of size $O(n^{3/2+\varepsilon})$ and can be found in a similar running time for any $\varepsilon>0$ .

1.2.5 Ordered graphs and visibility graphs

Visibility is a classical theme in computational geometry [35, Chapter 15] [46, 62]. A visibility graph is typically defined on a set of points in the plane, such that two points form an edge if and only if the line segment between them does not hit any obstacle. Polygon visibility graphs, for instance, are defined on the set of vertices of a simple closed polygon, and two vertices are adjacent in the graph if and only if the line segment between them is contained in the polygon. A notable result due to Agarwal, Alon, Aronov, and Suri [3] states that polygon visibility graphs have biclique partitions of size $O(n\log^{3}n)$ . The proof involves an reduction to bichromatic segment intersection graphs [28] and their compact representation based on segment trees by Chazelle et al. [27].

In what follows we consider ordered graphs, defined as graphs $G=(V,E)$ where the set of vertices $V$ is totally ordered. For simplicity, we will often assume that $V=[n]=:\{1,2,\ldots,n\}$ with the natural ordering on $\mathbb{N}$ . An ordered graph $([n],E)$ is a capped graph if for any four vertices $i<j<k<\ell$ , if $ik\in E$ and $j\ell\in E$ , then $i\ell\in E$ [34]. See Figure 2 for an illustration.

Figure 2: The forbidden ordered subgraph in a capped graph. The dashed curve represents a non-edge: If

i k

and

j\ell

are edges, then

i\ell

must be an edge.

This property is also sometimes referred to as the $X$ -property, and capped graphs are also referred to as terrain-like graphs [43, 12, 45].

A terrain visibility graph is defined on the set of vertices of an $x$ -monotone polygonal line in the plane, also called a terrain, where two vertices are adjacent in the graph if and only if the open line segment between them lies completely above the terrain [1, 40, 11, 52]. Terrain visibility graphs have applications to time series analysis [56], and have been used for instance in medical contexts [9, 72].

It is not difficult to realize that terrain visibility graphs are capped graphs. Indeed, if we are given four points in the order $i<j<k<\ell$ along the terrain such that there is a line of sight between $i$ and $k$ and between $j$ and $\ell$ , then there must be one between $i$ and $\ell$ . In fact, capped graphs also contain induced subgraphs of terrain visibility graphs, as well as visibility graphs involving points on an arbitrary, not necessary polygonal, $x$ -monotone curve. See Figure 3 for an example.

Figure 3: The visibility graph of a set of points on an

x

-monotone curve. When vertices are ordered from left to right, this is an example of capped graph.

Persistent graphs are capped graphs that also satisfy the so-called bar property: for any edge of the form $i k$ such that $k\geq i+2$ , there exists $j$ such that $i<j<k$ and both $i j$ and $j k$ are also edges [11, 44]. It is known that terrain visibility graphs are also persistent, and it was once conjectured that they form the same class. This conjecture was disproved by Ameer, Gibson-Lopez, Krohn, Soderman, and Wang [11].

Algorithms on terrain visibility graphs and terrain-like graphs have been studied by Katz, Saban, and Sharir [53], Froese and Renken [43], and De Berg, Van Beusekom, Van Mulken, Verbeek, and Wulms [36]. The Zarankiewicz problem for polygon visibility graphs was recently studied by Ackerman and Keszegh [2].

1.3 Plan of the paper

In Section 2, we construct near-linear biclique partitions for comparability graphs and bigraphs of bounded dimension. This will be used as a building block for many of the subsequent results. In Section 3, we state and prove our main result on the existence and construction of near-linear biclique partitions for any semilinear graphs. In Section 4, we give our main result on terrain-like graphs. In Section 5 we consider lower bounds on the size of biclique covers.

2 $𝒅$ -dimensional comparability graphs

A graph $G=(V,E)$ is a comparability graph if there exists a partial ordering $P(G)$ of $V$ such that two vertices are adjacent if and only if they are comparable in $P(G)$ . One may wonder if comparability graph could have small biclique covers. A simple counting argument rules this out: all bipartite graphs are comparability graphs, and there are $2^{\Omega(n^{2})}$ bipartite graphs on $n$ vertices. From Observation 3, there must exist comparability graphs all biclique covers of which have size $\Omega(n^{2}/\log n)$ , which from Theorem 1 is not better than for general graphs.

We therefore restrict our attention to $d$ -dimensional comparability graphs. A partial ordering $P$ has dimension $d$ if there is a collection $\mathcal{L}=\{L_{1},L_{2},\ldots,L_{d}\}$ of linear extensions of $P$ such $P=\bigcap_{i=1}^{d}L_{i}$ . A comparability graph $G$ has dimension $d$ if there is a partial ordering $P(G)$ of $V$ of dimension $d$ . Equivalently, a $d$ -dimensional comparability graph is a graph $G=(V,E)$ for which there exists a map $\varphi:V\mapsto\mathbb{R}^{d}$ such that any two vertices $v,u\in V$ are adjacent if and only if they are comparable with respect to $\varphi$ , that is either $\varphi(v)\prec\varphi(u)$ or $\varphi(v)\succ\varphi(u)$ , where $a\prec b$ if and only if $a_{i}<b_{i}$ for all $i\in[d]$ . We can assume without loss of generality that no pair of points in $\varphi(V)$ share a coordinate. See Figure 4 for an example of a two-dimensional comparability graph. Note that two-dimensional comparability graphs are also known as permutation graphs [16].

(a) A two-dimensional comparability graph.

(b) A two-dimensional comparability bigraph.

Figure 4: Comparability graphs and bigraphs.

We also define a bipartite version of a $d$ -dimensional comparability graph. A $d$ -dimensional comparability bigraph is a bipartite graph $G=(L\cup R,E)$ for which there exists a map $\varphi:L\cup R\mapsto\mathbb{R}^{d}$ such that no pair of points in $\varphi(L)\times\varphi(R)$ share a coordinate, and such that for any pair $(\ell,r)\in L\times R$ , $\ell r\in E$ if and only if $\varphi(\ell)\prec\varphi(r)$ . We also adopt the convention that $0$ -dimensional comparability bigraphs are complete bipartite graphs, where $E=L\times R$ . See Figure 4 for an example of a two-dimensional comparability graph. For both graph classes, we refer to the function $\varphi$ as the embedding map of $G$ .

We proceed by showing two key theorems concerning the size of a biclique cover of $d$ -dimensional comparability bigraphs and graphs. The proofs rely on a simple induction for the dominating pairs problem [65, 22].

Theorem 8.

Any $d$ -dimensional comparability bigraph on $n$ vertices has a biclique partition of size $O(n\log^{d}n)$ .

Proof.

We prove the theorem by induction on $d$ . For $d=0$ , the bigraph is a biclique, hence has a trivial partition of size $O(n)$ .

Now let $d\geq 1$ and assume that the theorem holds for any $d^{\prime}<d$ . Let $G$ be a $d$ -dimensional comparability bigraph and let $\varphi$ be its embedding map in $\mathbb{R}^{d}$ . Let $p\in\mathbb{R}$ be a point on the $d$ th axis such that the orthogonal hyperplane $H$ through $p$ divides the points in $L\cup R$ into two parts of size at most $\lceil n/2\rceil$ . Let $\varphi_{d}$ be the restriction of $\varphi$ to the $d$ th coordinate and let $\varphi_{1,\ldots,d-1}$ be the restriction of $\varphi$ to the first $(d-1)$ coordinates. Let $L^{\prime}\subseteq L$ be the set of vertices $\ell\in L$ for which $\varphi_{d}(\ell)<p$ and let $R^{\prime}\subseteq R$ be the of vertices $r\in R$ for which $\varphi_{d}(r)>p$ . Observe that $\ell r\in E$ , for $\ell\in L^{\prime}$ and $r\in R^{\prime}$ , if and only if $\varphi_{1,\ldots,d-1}(\ell)\prec\varphi_{1,\ldots,d-1}(r)$ . Let $G^{\prime}$ be a $(d-1)$ -dimensional comparability bipartite subgraph of $G$ induced on $L^{\prime}\cup R^{\prime}$ with the embedding map $\varphi_{1,\ldots,d-1}$ obtained by projecting those points on $H$ . By induction, $G^{\prime}$ has a biclique partition of size $O(n\log^{d-1}n)$ . It remains to recurse twice on each side of $H$ with half the points. Let $S(n)$ be the size of a biclique partition of $G$ . The total size $S(n)$ therefore obeys the recurrence

S(n)\leq 2S(\lceil n/2\rceil)+O(n\log^{d-1}n)=O(n\log^{d}n).\

$\hfill\blacktriangleleft$

The same method gives an upper bound on the size of a biclique partition of $d$ -dimensional comparability graphs. We omit the proof here.

Theorem 9.

Any $d$ -dimensional comparability graph on $n$ vertices has a biclique partition of size $O(n\log^{d}n)$ .

3 Semilinear graphs

Semilinear graphs were recently introduced by Basit, Chernikov, Starchenko, Tao and Tran [13], and form a subclass of semialgebraic graphs. A graph $G=(V,E)$ is a semilinear graph of complexity $t$ if the vertices in $V$ can be mapped to points in $\mathbb{R}^{d}$ and there exist $t$ linear functions $f_{1},\ldots,f_{t}:\mathbb{R}^{d}\times\mathbb{R}^{d}\rightarrow\mathbb{R}$ such that the edges of $G$ are defined by the sign patterns of those functions. More precisely, let F and T denote false and true respectively. Then $G$ is semilinear if there exist:

$\blacksquare$

a map $\varphi:V\mapsto\mathbb{R}^{d}$ ,
$\blacksquare$

$t$ linear functions $f_{1},\ldots,f_{t}\in\mathbb{R}[x_{1},\ldots,x_{d},y_{1},\ldots y_{d}]$ in $2d$ variables,
$\blacksquare$

a boolean function $\Phi:\{\text{T},\text{F}\}^{3t}\rightarrow\{\text{T},\text{F}\}$ ,

such that for any $u,v\in V$ ,

uv\in E\Leftrightarrow\Phi\left(\{f_{i}(\varphi(u),\varphi(v))<0,f_{i}(\varphi% (u),\varphi(v))=0,f_{i}(\varphi(u),\varphi(v))\leq 0\}_{i\in[t]}\right)=T.

The bounded-dimensional comparability graphs of the previous section are simple examples of semilinear graphs. Interval graphs are another. Indeed, two intervals $[a,b]$ and $[c,d]$ intersect if and only if $a\leq d$ and $b\geq c$ . A similar condition can be written for the intersection of two boxes in $\mathbb{R}^{d}$ . Furthermore the union of constantly many such graphs is also a semilinear graph.

Tomon [73] observed that we can restrict the definition above to boolean formulas in disjunctive normal form, and involving only strict inequalities. A graph $G=(V,E)$ is dnf-semilinear of complexity $(t,\ell)$ if there exist a map $\varphi:V\mapsto\mathbb{R}^{d}$ and $t\cdot\ell$ linear functions $f_{i,j}:\mathbb{R}^{d}\times\mathbb{R}^{d}\rightarrow\mathbb{R}$ , $(i,j)\in[\ell]\times[t]$ , such that for any $u,v\in V$ ,

uv\in E\Leftrightarrow\bigvee_{i\in[\ell]}\left(\bigwedge_{j\in[t]}f_{i,j}(% \varphi(u),\varphi(v))<0\right)=T.

(1)

As shown in [73], any semilinear graph of complexity $t$ is a dnf-semilinear graph of complexity $(t^{\prime},\ell)$ where $t^{\prime}$ and $\ell$ depend only on $t$ , and therefore the two definitions are essentially equivalent. The second definition will be useful in our proofs.

Theorem 10.

Let $G=(V,E)$ be a semilinear graph of constant complexity on $n$ vertices. Then $G$ has a biclique cover of size $O(n\operatorname{\mathrm{polylog}}n)$ .

Proof.

From the above discussion, we can assume that $G$ is dnf-semilinear of complexity $(t,\ell)$ , for some constants $t$ and $\ell$ . Consider a function $f_{i,j}$ appearing in this definition, for some $(i,j)\in[\ell]\times[t]$ . Since $f_{i,j}$ is linear, we can rewrite it as $f_{i,j}(x,y)=g_{i,j}(x)+h_{i,j}(y)$ with suitable functions $g_{i,j},h_{i,j}:\mathbb{R}^{d}\rightarrow\mathbb{R}$ . Let $g_{i}(x)=(g_{i,1}(x),\ldots,g_{i,t}(x))$ and $h_{i}(x)=(h_{i,1}(x),\ldots,h_{i,t}(x))$ . Now the condition $f_{i,j}(x,y)<0$ can be rewritten $g_{i,j}(x)<-h_{i,j}(x)$ , and

\bigwedge_{j\in[t]}f_{i,j}(x,y)<0\Leftrightarrow g_{i}(x)\prec-h_{i}(y).

This condition defines a subgraph $G_{i}$ of $G$ whose edges are the pairs $u,v\in V$ such that either $g_{i}(\varphi(u))\prec-h_{i}(\varphi(v))$ or $g_{i}(\varphi(v))\prec-h_{i}(\varphi(u))$ .

We now show that $G_{i}$ has a biclique partition of size $O(n\log^{t+1}n)$ . Let us split the set $V$ of vertices into two subsets $L$ and $R$ of size at most $\lceil n/2\rceil$ . The graph whose edges are the pairs $(u,v)\in L\times R$ such that $g_{i}(\varphi(u))\prec-h_{i}(\varphi(v))$ is a $t$ -dimensional comparability bigraph. Similarly, the graph whose edges are the pairs $(u,v)\in L\times R$ such that $-h_{i}(\varphi(u))\succ g_{i}(\varphi(v))$ is also a $t$ -dimensional comparability bigraph. These two graphs cover the edges of $G_{i}$ that are in the cut $(L,R)$ . From Theorem 9, they each have a biclique cover of size $O(n\log^{t}n)$ . It remains to cover the edges contained in $L$ and $R$ recursively. This yields a biclique cover of size $O(n\log^{t+1}n)$ , proving our claim.

$G$ is the union of the $\ell$ graphs $G_{i}$ for $i\in[\ell]$ . Taking the union of the biclique covers for each of the $G_{i}$ yields a biclique cover of size $O(n\log^{t+1}n)$ for $G$ , as required. $\hfill\blacktriangleleft$

Combined with Observation 2, this directly implies the result from Basit, Chernikov, Starchenko, Tao, and Tran [13].

Corollary 11 ([13]).

Let $G$ be a semilinear graph without a $K_{t,t}$ subgraph, for some $t\in\mathbb{N}$ . Then $G$ has at most $O(n\operatorname{\mathrm{polylog}}n)$ edges.

Also note that the proof of Theorem 10 provides a construction algorithm running in time proportional to the output size. This holds provided that the $d$ -dimensional comparability bigraph in Theorem 8 and the semilinear graph in Theorem 10 are given in the following implicit form: Every vertex is encoded as a point in $\mathbb{R}^{d}$ , and the functions determining the presence of an edge are encoded in constant space.

Lemma 12.

Given a semilinear graph $G$ of constant complexity, we can compute a biclique partition of $G$ of size $O(n\operatorname{\mathrm{polylog}}n)$ in time $O(n\operatorname{\mathrm{polylog}}n)$ .

Combining Lemma 12 with the known computational results of Lemmas 4 and 5, we obtain the following.

Theorem 13.

Given a semilinear graph $G$ of constant complexity on $n$ vertices, we can compute a maximum matching of $G$ in time $O(n^{1+\varepsilon})$ , and solve the all-pairs shortest path problem on $G$ in time $O(n^{2}\operatorname{\mathrm{polylog}}n)$ .

4 Terrain-like graphs

Recall that capped graphs, also known as terrain-like graphs, are ordered graphs such that for any four vertices $i<j<k<\ell$ , if both $i k$ and $j\ell$ are edges, then so is $i\ell$ . We first define the bipartite counterpart of capped graphs, that we call capped bigraphs, as ordered bipartite graphs $G=(L\cup R,E)$ , where the elements in $L$ appear before the elements in $R$ in the order, and that satisfy the same property, that is for all $i<j\in L$ and $k<\ell\in R$ , we have that if $ik\in E$ and $j\ell\in E$ , then $i\ell\in E$ .

Lemma 14.

Every capped bigraph is a two-dimensional comparability bigraph.

Proof.

Let $G=(L\cup R,E)$ be a capped bigraph. We assume for now that $G$ does not have any isolated vertex. Let us suppose, without loss of generality, that $L,R\subset\mathbb{N}$ . Consider the map $\varphi:L\cup R\mapsto\mathbb{R}^{2}$ defined as

\varphi(\ell)=(\ell,\min\{r^{\prime}\in R:\ell r^{\prime}\in E\}-1/2)

for any $\ell\in L$ , and

\varphi(r)=(\max\{\ell^{\prime}\in L:\ell^{\prime}r\in E\}+1/2,r),

for any $r\in R$ . We claim that $\ell r\in E$ if and only if $\varphi(\ell)\prec\varphi(r)$ .

We first show that if $\ell r\in E$ , then $\varphi(\ell)\prec\varphi(r)$ . Indeed, if $\ell r\in E$ , it must be the case that $\ell<\max\{\ell^{\prime}:\ell^{\prime}r\in E\}+1/2$ . Similarly, it must be the case that $\min\{r^{\prime}:\ell r^{\prime}\in E\}-1/2<r$ . Hence the point $\varphi(\ell)$ is dominated by $\varphi(r)$ .

Conversely, suppose that $\varphi(\ell)\prec\varphi(r)$ . Let $\ell^{*}=\max\{\ell^{\prime}:\ell^{\prime}r\in E\}$ and $r^{*}=\min\{r^{\prime}:\ell r^{\prime}\in E\}$ . If either $\ell^{*}=\ell$ or $r^{*}=r$ , then we have $\ell r\in E$ by definition. Let us therefore suppose that $\ell^{*}\not=\ell$ and $r^{*}\not=r$ . Then, since $\varphi(\ell)\prec\varphi(r)$ , we have $\ell<\ell^{*}$ and $r^{*}<r$ . By definition, $\ell r^{*}\in E$ and $\ell^{*}r\in E$ , hence from the X-property of capped bigraphs, it must be the case that $\ell r\in E$ as well.

Finally, note that isolated vertices can easily be added, by assigning them either a very large vertical or horizontal coordinate. $\hfill\blacktriangleleft$

(a) A capped bigraph obtained from the example of Figure 3, together with the values of

\varphi(u)

for each vertex

u

.

(b) A representation of the capped bigraph as a two-dimensional comparability bigraph.

(c) A representation of the capped bigraph as a two-directional orthogonal ray graph.

Figure 5: Illustration of the proof of Lemma 14.

The proof is illustrated in Figure 5. Note that conversely, any two-dimensional comparability bigraph $(L\cup R,E)$ , as witnessed by a map $\varphi$ , is a capped bigraph, where the order of the vertices in $L$ and $R$ is given respectively by the $x$ and $y$ -coordinates of the points in the image of the map $\varphi$ . It suffices to observe that the $X$ -property is satisfied. One can observe that this class of bigraphs is in fact the same as that of interval containment bigraphs in Huang [50] and Hell, Huang, Lin, and McConnell [49], and two-directional orthogonal ray graphs studied by Shrestha, Tayu, and Ueno [69]. Therefore, capped bigraphs, two-dimensional comparability bigraphs, interval containment bigraphs, and two-directional orthogonal ray graphs are one and the same class. The equivalence with two-directional orthogonal ray graphs is immediate: Suppose that the vertical rays extend upwards and the horizontal rays extend to the left, and observe that a vertical ray $v$ intersects a horizontal ray $h$ if and only if the origin of $v$ is dominated by the origin of $h$ .

Theorem 15.

Every capped graph on $n$ vertices admits a biclique cover of size $O(n\log^{3}n)$ .

Proof.

Consider a capped graph $G=([n],E)$ and let $L:=[\lfloor n/2\rfloor]$ and $R=[n]\setminus L$ . Let $F=\{ij\in E:i\in L,j\in R\}$ . By definition, $H:=(L\cup R,F)$ is a capped bigraph. From Lemma 14 and Theorem 8, $H$ admits a biclique cover of size $O(n\log^{2}n)$ . It remains to cover the edges of the two subgraphs $G[L]$ and $G[R]$ , which are also capped graphs. This can be done recursively, yielding a total size of $S(n)\leq 2S(\lceil n/2\rceil)+O(n\log^{2}n)=O(n\log^{3}n)$ , as claimed. $\hfill\blacktriangleleft$

We now consider the computational problem of constructing a biclique cover of size $O(n\log^{3}n)$ of a capped graph given as input. The natural encoding of the input graph can be of size proportional to the number of edges. Remember that capped graphs are ordered graphs. We can suppose that a capped graph is given in sorted adjacency list representation, in which not only the order of the vertices is given, but we are also given the neighbors of each vertex in sorted order. Note that sorting adjacency lists requires an additional cost of $O(|E|\log\log n)$ , since the numbers to sort lie in the range $[n]$ [77].

Lemma 16.

Given a capped graph $G=(V,E)$ in sorted adjacency list representation, we can compute a biclique partition of $G$ of size $O(n\log^{3}n)$ in time $O(\max\{|E|,n\log^{3}n\})$ .

Proof.

We follow the proof of Theorem 15. Given a bipartition of the vertices of $G$ into the sets $L$ and $R$ , we need to efficiently compute the implicit representation of the corresponding comparability bigraph, as described in the proof of Lemma 14. This requires finding, for each vertex $\ell$ in $L$ , the smallest index $r\in R$ such that $\ell r\in E$ , and conversely for every vertex in $R$ . This can be achieved by storing adjacency lists in binary search trees, for instance, which can be done in linear time if they are sorted. $\hfill\blacktriangleleft$

We can then for instance combine Lemma 16 with Lemma 4.

Theorem 17.

Given a capped graph $G$ on $n$ vertices in sorted adjacency list representation, we can solve the all-pairs shortest path problem on $G$ in time $O(n^{2}\operatorname{\mathrm{polylog}}n)$ . Furthermore, after a $O(\max\{|E|,n\log^{3}n\})$ -time preprocessing, one can construct the breadth-first search tree rooted at any vertex in time $O(n\log^{3}n)$ .

5 Lower bounds

It is known that there exist configurations of $n$ points and $n$ lines with $\Theta(n^{4/3})$ point-line incidences, hence that are tight examples for the Szemerédi-Trotter incidence bound; see for instance the construction from Erdős described in Edelsbrunner [38]. From Observation 2, we have that the size $s$ of a biclique cover for a graph $G=(V,E)$ without $K_{t,t}$ for some constant $t$ must satisfy $s\geq|E|/t$ . Clearly, point-line incidence graphs do not have $K_{2,2}$ subgraphs, hence there exist such graphs on $n$ vertices for which $s\geq\Omega(n^{4/3})$ . We first prove a similar statement for incidence graphs of points and halfplanes in $\mathbb{R}^{2}$ . The proof is essentially the same as that of Erickson [39, Theorem 3.4].

Lemma 18.

There exist incidence graphs between $n$ points and $n$ closed lower halfplanes, any biclique cover of which has size $\Omega(n^{4/3})$ .

Proof.

We consider a configuration $(P,L)$ of $n$ points and $n$ lines with $\Theta(n^{4/3})$ point-line incidences. Let $H$ be the set of closed lower halfplanes bounded by the lines of $L$ . We denote by $I(P,H)$ the incidence graph between the points of $P$ and the halfplanes of $H$ .

Let $P_{i}\subseteq P$ and $H_{i}\subseteq H$ be the two sets of vertices in the $i$ th biclique of a biclique cover of $I(P,H)$ . Let $L_{i}\subseteq L$ be the lines bounding the halfspaces of $H_{i}$ , and let us denote by $\iota(P_{i},L_{i})$ the number of pairs $(p,\ell)\in P_{i}\times L_{i}$ such that $p\in\ell$ .

Claim 19.

|P_{i}|+|H_{i}|\geq\iota(P_{i},L_{i}).

Proof of claim..

Let $R_{i}$ denote the intersection of the lower halfplanes in $H_{i}$ . By definition, $R_{i}$ is a downward closed convex polygonal region, and $P_{i}\subset R_{i}$ .

Consider the leftmost incidence $(p,\ell)$ in $(P_{i},L_{i})$ , involving the leftmost point with the leftmost line. Suppose that $p$ is incident to more than one line. It must then be the case that $\ell$ does not contain any other point than $p$ . Hence either $p$ is incident to only one line, or $\ell$ contains only one point. We can therefore always remove either a point or a line and remove one incidence. The number of incidences is then at most $|P_{i}|+|L_{i}|=|P_{i}|+|H_{i}|$ , as claimed. $\hfill\vartriangleleft$

We now obtain a lower bound on the size of the biclique cover as follows:

\sum_{i}|P_{i}|+|H_{i}|\geq\sum_{i}\iota(P_{i},L_{i})\geq\iota(P,L)\geq\Omega(% n^{4/3}).

where the second inequality is from the fact that every incidence in $(P,L)$ is an edge of $I(P,H)$ , hence must be covered by at least one of the biclique. $\hfill\blacktriangleleft$

We now turn our attention to unit disk graphs, which are perhaps among the simplest non-semilinear geometric intersection graphs.

Lemma 20.

There exist unit disk graphs on $n$ vertices, any biclique cover of which has size $\Omega(n^{4/3})$ .

Proof.

It is enough to show that the incidence graph $I(P,H)$ in the proof of Lemma 18 can be realized with unit disks. Indeed, take the configuration $(P,L)$ and shift every line of $L$ upwards by a small vertical offset, so that the points involved in the incidences lie now slightly below their lines. We can now safely replace these lines by circles of the same very large radius, keeping the points of $P$ in the same relative positions with respect to each of the lines. Let $Q$ denote the set of centers of the circles. By a proper scaling, we can assume without loss of generality that those circles have radius two.

Observe that if a graph $G$ has a biclique cover of size $s$ , then any bipartite graph obtained from $G$ by coloring the vertices in two colors and removing all monochromatic edges also has a biclique cover of size $s$ . It is therefore sufficient to prove a lower bound on the size of a biclique cover of the bipartite intersection graph of the unit disks of centers respectively in $P$ and $Q$ . By construction, this is exactly the point-halfplane incidence graph $I(P,H)$ , and we can now apply the result of Lemma 18. $\hfill\blacktriangleleft$

Note that a similar statement should hold for intersection graphs of translates of any smooth strictly convex body.

One may also wonder if there exists superlinear lower bounds on the size of biclique covers for families of semilinear graphs. We can easily deduce such a lower bound from a recent result from Bhore et al. [14].

Lemma 21.

There exist graphs on $n$ vertices and boxicity at most $d$ , any biclique cover of which has size $\Omega(n(\log n/\log\log n)^{d-2})$ .

Proof.

A construction from Bhore et al. [14] shows that there exist intersection graphs of $n$ boxes in dimension $d$ such that any 3-hop spanners requires $\Omega(n(\log n/\log\log n)^{d-2})$ edges. From Lemma 6, it implies the same lower bound on the size of their biclique covers. $\hfill\blacktriangleleft$

6 Open questions

Many open questions remain. We showed a few upper bounds on the size of the biclique cover for restricted families of semilinear graphs, such as intersection graphs of axis-aligned boxes and grounded L-shapes (see the full version of the paper for the definition and the bound on intersection graphs of grounded L-shapes [20]). These bounds improve upon those that can be derived from the general upper bound for semilinear graphs. A first natural question is whether any of those bounds can be improved or, alternatively, what are the achievable lower bounds on the size of a biclique cover for these graphs. The question of improving the upper bound also remains for capped graphs; do capped graphs admit $O(n\log^{2}n)$ -size biclique covers?

For both capped and non-jumping graphs we showed an upper bound of $O(n\log^{3}n)$ on the size of their biclique cover. Recall that capped and non-jumping graphs are graphs equipped with an ordering on their vertices such that for any four vertices $i<j<k<\ell$ , if $i k$ and $j\ell$ are edges, then the edge $i\ell$ must also be present in a capped graph, and the edge $j k$ must be present in a non-jumping graph. There is an interesting superclass of both capped and non-jumping graphs, in which given four vertices $i<j<k<\ell$ such that $i k$ and $j\ell$ are edges, either the edge $i\ell$ or $j k$ must be present. In particular, they contain the terrain visibility graphs considered by Katz, Saban, and Sharir [53], in which points lying strictly above the terrain are also allowed as vertices. Do these ordered graphs admit biclique covers of small size?

More generally, it would be interesting to characterize the forbidden patterns which give rise to families of (ordered) graphs for which the size of a biclique cover is $O(n\text{ poly}\log n)$ . Note that there are forbidden patterns of size $3$ for which the family of graphs which forbids them does not have such a bound. For example, $3$ vertices which induce a triangle.

Finally, in this work we mostly focused on graph classes that are either arising in a geometric setting or forbid some ordered patterns. It would be interesting to understand how the size of a clique cover correlates with other width parameters of graphs, for example, the twin-width of a graph [15].

References

[1] James Abello, Ömer Eğecioğlu, and Krishna Kumar. Visibility graphs of staircase polygons and the weak Bruhat order. I. From visibility graphs to maximal chains. Discrete Comput. Geom., 14(3):331–358, 1995. doi:10.1007/BF02570710.
[2] Eyal Ackerman and Balázs Keszegh. The Zarankiewicz Problem for Polygon Visibility Graphs. arXiv preprint arXiv:2503.09115, 2025. doi:10.48550/arXiv.2503.09115.
[3] Pankaj K. Agarwal, Noga Alon, Boris Aronov, and Subash Suri. Can visibility graphs be represented compactly? Discrete Comput. Geom., 12(3):347–365, 1994. doi:10.1007/BF02574385.
[4] Pankaj K. Agarwal, Boris Aronov, Esther Ezra, Matthew J. Katz, and Micha Sharir. Intersection queries for flat semi-algebraic objects in three dimensions and related problems. In Xavier Goaoc and Michael Kerber, editors, 38th International Symposium on Computational Geometry, SoCG 2022, June 7-10, 2022, Berlin, Germany, volume 224 of LIPIcs, pages 4:1–4:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPICS.SOCG.2022.4.
[5] Pankaj K. Agarwal, Boris Aronov, Esther Ezra, Matthew J. Katz, and Micha Sharir. Intersection queries for flat semi-algebraic objects in three dimensions and related problems. arXiv preprint 2203.10241, 2025. doi:10.48550/arXiv.2203.10241.
[6] Pankaj K. Agarwal and Jeff Erickson. Geometric range searching and its relatives. Contemporary Mathematics, 223(1):56, 1999. doi:10.1090/conm/223/03131.
[7] Pankaj K. Agarwal, Esther Ezra, and Micha Sharir. Semi-algebraic off-line range searching and biclique partitions in the plane. In Wolfgang Mulzer and Jeff M. Phillips, editors, 40th International Symposium on Computational Geometry, SoCG 2024, June 11-14, 2024, Athens, Greece, volume 293 of LIPIcs, pages 4:1–4:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPICS.SOCG.2024.4.
[8] Pankaj K. Agarwal and Kasturi R. Varadarajan. Efficient algorithms for approximating polygonal chains. Discrete Comput. Geom., 23(2):273–291, 2000. doi:10.1007/PL00009500.
[9] Adeli A. Ahmadlou M., Adeli H. New diagnostic EEG markers of the Alzheimer’s disease using visibility graph. J. Neural Transm., 117:1099–1109, 2010. doi:10.1007/s00702-010-0450-3.
[10] Noga Alon, János Pach, Rom Pinchasi, Radoš Radoičić, and Micha Sharir. Crossing patterns of semi-algebraic sets. J. Combin. Theory Ser. A, 111(2):310–326, 2005. doi:10.1016/j.jcta.2004.12.008.
[11] Safwa Ameer, Matt Gibson-Lopez, Erik Krohn, Sean Soderman, and Qing Wang. Terrain visibility graphs: persistence is not enough. In 36th International Symposium on Computational Geometry, volume 164 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 6, 13. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020. doi:10.4230/LIPICS.SOCG.2020.6.
[12] Stav Ashur, Omrit Filtser, Matthew J. Katz, and Rachel Saban. Terrain-like graphs: PTASs for guarding weakly-visible polygons and terrains. Comput. Geom., 101:Paper No. 101832, 13, 2022. doi:10.1016/j.comgeo.2021.101832.
[13] Abdul Basit, Artem Chernikov, Sergei Starchenko, Terence Tao, and Chieu-Minh Tran. Zarankiewicz’s problem for semilinear hypergraphs. In Forum of Mathematics, Sigma, volume 9, page e59. Cambridge University Press, 2021. doi:10.1017/fms.2021.52.
[14] Sujoy Bhore, Timothy M. Chan, Zhengcheng Huang, Shakhar Smorodinsky, and Csaba D. Tóth. Sparse bounded hop-spanners for geometric intersection graphs. arXiv preprint arXiv:2504.05861, 2025. doi:10.48550/arXiv.2504.05861.
[15] Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. Twin-width I: tractable fo model checking. ACM Journal of the ACM (JACM), 69(1):1–46, 2021. doi:10.1145/3486655.
[16] Andreas Brandstädt, Van Bang Le, and Jeremy P. Spinrad. Graph classes: a survey. SIAM Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1999. doi:10.1137/1.9780898719796.
[17] Peter Braß and Christian Knauer. On counting point-hyperplane incidences. Computational Geometry, 25(1-2):13–20, 2003. doi:10.1016/S0925-7721(02)00127-X.
[18] Sergio Cabello, Siu-Wing Cheng, Otfried Cheong, and Christian Knauer. Geometric matching and bottleneck problems. In 40th International Symposium on Computational Geometry, SoCG 2024, June 11-14, 2024, Athens, Greece, pages 31:1–31:15, 2024. doi:10.4230/LIPICS.SOCG.2024.31.
[19] Jean Cardinal and Micha Sharir. Improved algebraic degeneracy testing. Discrete & Computational Geometry, pages 1–19, 2024. doi:10.1007/s00454-024-00673-7.
[20] Jean Cardinal and Yelena Yuditsky. Compact representation of semilinear and terrain-like graphs. arXiv preprint arXiv:2507.00252, 2025. doi:10.48550/arXiv.2507.00252.
[21] Timothy M. Chan. Dynamic subgraph connectivity with geometric applications. SIAM Journal on Computing, 36(3):681–694, 2006. doi:10.1137/S009753970343912X.
[22] Timothy M. Chan. All-pairs shortest paths with real weights in $O(n^{3}/\log n)$ Time. Algorithmica, 50(2):236–243, 2008. doi:10.1007/S00453-007-9062-1.
[23] Timothy M. Chan. Optimal partition trees. Discrete Comput. Geom., 47(4):661–690, 2012. doi:10.1007/s00454-012-9410-z.
[24] Timothy M Chan, Pingan Cheng, and Da Wei Zheng. Semialgebraic range stabbing, ray shooting, and intersection counting in the plane. In 40th International Symposium on Computational Geometry, SoCG 2024, page 33. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, 2024. doi:10.4230/LIPIcs.SoCG.2024.33.
[25] Timothy M. Chan and Dimitrios Skrepetos. All-pairs shortest paths in geometric intersection graphs. J. Comput. Geom., 10(1):27–41, 2019. doi:10.20382/JOCG.V10I1A2.
[26] Bernard Chazelle. Cutting hyperplanes for divide-and-conquer. Discrete Comput. Geom., 9(2):145–158, 1993. doi:10.1007/BF02189314.
[27] Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas, and Micha Sharir. Algorithms for bichromatic line-segment problems polyhedral terrains. Algorithmica, 11(2):116–132, 1994. doi:10.1007/BF01182771.
[28] Bernard Chazelle and Leonidas J. Guibas. Visibility and intersection problems in plane geometry. Discret. Comput. Geom., 4:551–581, 1989. doi:10.1007/BF02187747.
[29] Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva. Maximum flow and minimum-cost flow in almost-linear time. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022, pages 612–623. IEEE, 2022. doi:10.1109/FOCS54457.2022.00064.
[30] Fan R. K. Chung, Paul Erdős, and Joel Spencer. On the decomposition of graphs into complete bipartite subgraphs. In Studies in pure mathematics, pages 95–101. Birkhäuser, Basel, 1983. doi:10.1007/978-3-0348-5438-2_10.
[31] David Conlon. Some remarks on the Zarankiewicz problem. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 173(1), pages 155–161. Cambridge University Press, 2022. doi:10.1017/S0305004121000475.
[32] David Conlon, Jacob Fox, János Pach, Benny Sudakov, and Andrew Suk. Ramsey-type results for semi-algebraic relations. Trans. Amer. Math. Soc., 366(9):5043–5065, 2014. doi:10.1090/S0002-9947-2014-06179-5.
[33] Jonathan B. Conroy and Csaba D. Tóth. Hop-spanners for geometric intersection graphs. J. Comput. Geom., 14(2):26–64, 2022. doi:10.20382/JOCG.V14I2A3.
[34] James Davies, Tomasz Krawczyk, Rose McCarty, and Bartosz Walczak. Coloring polygon visibility graphs and their generalizations. J. Combin. Theory Ser. B, 161:268–300, 2023. doi:10.1016/j.jctb.2023.02.010.
[35] Mark de Berg, Otfried Cheong, Marc J. van Kreveld, and Mark H. Overmars. Computational geometry: algorithms and applications, 3rd Edition. Springer, 2008. doi:10.1007/978-3-540-77974-2.
[36] Sarita de Berg, Nathan van Beusekom, Max van Mulken, Kevin Verbeek, and Jules Wulms. Competitive searching over terrains. In José A. Soto and Andreas Wiese, editors, LATIN 2024: Theoretical Informatics - 16th Latin American Symposium, Puerto Varas, Chile, March 18-22, 2024, Proceedings, Part I, volume 14578 of Lecture Notes in Computer Science, pages 254–269. Springer, 2024. doi:10.1007/978-3-031-55598-5_17.
[37] Thao Do. Representation complexities of semialgebraic graphs. SIAM J. Discrete Math., 33(4):1864–1877, 2019. doi:10.1137/18M1221606.
[38] Herbert Edelsbrunner. Algorithms in combinatorial geometry, volume 10 of EATCS Monographs on Theoretical Computer Science. Springer-Verlag, Berlin, 1987. doi:10.1007/978-3-642-61568-9.
[39] Jeff Erickson. New lower bounds for Hopcroft’s problem. Discrete & Computational Geometry, 16(4):389–418, 1996. doi:10.1007/BF02712875.
[40] William Evans and Noushin Saeedi. On characterizing terrain visibility graphs. J. Comput. Geom., 6(1):108–141, 2015. doi:10.20382/jocg.v6i1a5.
[41] Tomás Feder and Rajeev Motwani. Clique partitions, graph compression and speeding-up algorithms. J. Comput. System Sci., 51(2):261–272, 1995. doi:10.1006/jcss.1995.1065.
[42] Jacob Fox, János Pach, Adam Sheffer, Andrew Suk, and Joshua Zahl. A semi-algebraic version of Zarankiewicz’s problem. J. Eur. Math. Soc. (JEMS), 19(6):1785–1810, 2017. doi:10.4171/JEMS/705.
[43] Vincent Froese and Malte Renken. A fast shortest path algorithm on terrain-like graphs. Discrete Comput. Geom., 66(2):737–750, 2021. doi:10.1007/s00454-020-00226-8.
[44] Vincent Froese and Malte Renken. Persistent graphs and cyclic polytope triangulations. Comb., 41(3):407–423, 2021. doi:10.1007/S00493-020-4369-5.
[45] Vincent Froese and Malte Renken. Terrain-like graphs and the median Genocchi numbers. European J. Combin., 115:Paper No. 103780, 8, 2024. doi:10.1016/j.ejc.2023.103780.
[46] Subir K. Ghosh. Visibility Algorithms in the Plane. Cambridge University Press, 2007. doi:10.1017/CBO9780511543340.
[47] Oktay Günlük. A new min-cut max-flow ratio for multicommodity flows. SIAM Journal on Discrete Mathematics, 21(1):1–15, 2007. doi:10.1137/S089548010138917X.
[48] Larry Guth and Nets Hawk Katz. On the Erdős distinct distances problem in the plane. Ann. of Math. (2), 181(1):155–190, 2015. doi:10.4007/annals.2015.181.1.2.
[49] Pavol Hell, Jing Huang, Jephian C.-H. Lin, and Ross M. McConnell. Bipartite analogues of comparability and cocomparability graphs. SIAM J. Discrete Math., 34(3):1969–1983, 2020. doi:10.1137/19M1263789.
[50] Jing Huang. Representation characterizations of chordal bipartite graphs. J. Combin. Theory Ser. B, 96(5):673–683, 2006. doi:10.1016/j.jctb.2006.01.001.
[51] Stasys Jukna and Alexander S Kulikov. On covering graphs by complete bipartite subgraphs. Discrete Mathematics, 309(10):3399–3403, 2009. doi:10.1016/J.DISC.2008.09.036.
[52] Prahlad Narasimhan Kasthurirangan. One-sided terrain guarding and chordal graphs. Discrete Appl. Math., 348:192–201, 2024. doi:10.1016/j.dam.2024.01.034.
[53] Matthew J. Katz, Rachel Saban, and Micha Sharir. Near-linear algorithms for visibility graphs over a 1.5-dimensional terrain. In Timothy Chan, Johannes Fischer, John Iacono, and Grzegorz Herman, editors, 32nd Annual European Symposium on Algorithms (ESA 2024), volume 308 of Leibniz International Proceedings in Informatics (LIPIcs), pages 77:1–77:17, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ESA.2024.77.
[54] Matthew J. Katz and Micha Sharir. An expander-based approach to geometric optimization. SIAM J. Comput., 26(5):1384–1408, 1997. doi:10.1137/S0097539794268649.
[55] Oliver Kullmann and Ankit Shukla. Transforming quantified boolean formulas using biclique covers. In International Conference on Tools and Algorithms for the Construction and Analysis of Systems, pages 372–390. Springer, 2023. doi:10.1007/978-3-031-30820-8_23.
[56] Lucas Lacasa, Bartolo Luque, Fernando Ballesteros, Jordi Luque, and Juan Carlos Nuño. From time series to complex networks: The visibility graph. Proceedings of the National Academy of Sciences, 105(13):4972–4975, 2008. doi:10.1073/pnas.0709247105.
[57] Jiří Matoušek. Range searching with efficient hierarchical cuttings. In Proceedings of the eighth annual symposium on Computational geometry, pages 276–285, 1992. doi:10.1145/142675.142732.
[58] Jiří Matoušek. Cutting hyperplane arrangements. Discrete Comput. Geom., 6(5):385–406, 1991. doi:10.1007/BF02574697.
[59] Jiří Matoušek. Efficient partition trees. Discrete Comput. Geom., 8(3):315–334, 1992. ACM Symposium on Computational Geometry (North Conway, NH, 1991). doi:10.1007/BF02293051.
[60] Jiří Matoušek. Range searching with efficient hierarchical cuttings. Discrete Comput. Geom., 10(2):157–182, 1993. doi:10.1007/BF02573972.
[61] Jiří Matoušek and Zuzana Patáková. Multilevel polynomial partitions and simplified range searching. Discrete Comput. Geom., 54(1):22–41, 2015. doi:10.1007/s00454-015-9701-2.
[62] Joseph O’Rourke. Visibility. In Handbook of Discrete and Computational Geometry, 3rd Edition, chapter 33. Chapman and Hall/CRC, 2017. doi:10.1201/9781420035315.CH28.
[63] János Pach and Micha Sharir. Incidences. In Graph theory, combinatorics and algorithms, pages 267–292. Springer, New York, 2005. doi:10.1007/0-387-25036-0_11.
[64] Larry Palazzi and Jack Snoeyink. Counting and reporting red/blue segment intersections. CVGIP: Graphical Models and Image Processing, 56(4):304–310, 1994. doi:10.1006/cgip.1994.1027.
[65] Franco P. Preparata and Michael Ian Shamos. Computational geometry. Texts and Monographs in Computer Science. Springer-Verlag, New York, 1985. doi:10.1007/978-1-4612-1098-6.
[66] Vojtech Rödl and Andrzej Ruciński. Bipartite coverings of graphs. Combinatorics, Probability and Computing, 6(3):349–352, 1997. doi:10.1017/S0963548397003064.
[67] Lisa Sauermann. On the speed of algebraically defined graph classes. Advances in Mathematics, 380:107593, 2021. doi:10.1016/j.aim.2021.107593.
[68] Stephan Schwartz. An overview of graph covering and partitioning. Discrete Math., 345(8):Paper No. 112884, 17, 2022. doi:10.1016/j.disc.2022.112884.
[69] Anish Man Singh Shrestha, Satoshi Tayu, and Shuichi Ueno. On orthogonal ray graphs. Discrete Appl. Math., 158(15):1650–1659, 2010. doi:10.1016/j.dam.2010.06.002.
[70] Shakhar Smorodinsky. A survey of Zarankiewicz problems in geometry. arXiv preprint arXiv:2410.03702, 2024. doi:10.48550/arXiv.2410.03702.
[71] Andrew Suk. Semi-algebraic Ramsey numbers. J. Combin. Theory Ser. B, 116:465–483, 2016. doi:10.1016/j.jctb.2015.10.001.
[72] Xiaoying Tang, Li Xia, Yezi Liao, Weifeng Liu, Yuhua Peng, Tianxin Gao, and Yanjun Zeng. New approach to epileptic diagnosis using visibility graph of high-frequency signal. Clinical EEG and Neuroscience, 44(2):150–156, 2013. PMID: 23508995. doi:10.1177/1550059412464449.
[73] István Tomon. Ramsey properties of semilinear graphs. Israel Journal of Mathematics, 254(1):113–139, 2023. doi:10.1007/s11856-022-2390-7.
[74] Csaba D. Tóth. Weighted biclique covers. Open problem posed at the Tenth Annual Workshop on Geometry and Graphs (WoGaG’23), Bellairs Research Institute, 2023.
[75] Zsolt Tuza. Covering of graphs by complete bipartite subgraphs: complexity of $0$ - $1$ matrices. Combinatorica, 4(1):111–116, 1984. doi:10.1007/BF02579163.
[76] Jan van den Brand, Li Chen, Richard Peng, Rasmus Kyng, Yang P. Liu, Maximilian Probst Gutenberg, Sushant Sachdeva, and Aaron Sidford. A deterministic almost-linear time algorithm for minimum-cost flow. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023, pages 503–514. IEEE, 2023. doi:10.1109/FOCS57990.2023.00037.
[77] Peter van Emde Boas. Preserving order in a forest in less than logarithmic time. In 16th Annual Symposium on Foundations of Computer Science (Univ. California, Berkeley, Calif., 1975), pages 75–84. IEEE, Long Beach, CA, 1975. doi:10.1109/SFCS.1975.26.

[bib.bib1] [1] James Abello, Ömer Eğecioğlu, and Krishna Kumar. Visibility graphs of staircase polygons and the weak Bruhat order. I. From visibility graphs to maximal chains. Discrete Comput. Geom., 14(3):331–358, 1995. doi:10.1007/BF02570710.

[bib.bib2] [2] Eyal Ackerman and Balázs Keszegh. The Zarankiewicz Problem for Polygon Visibility Graphs. arXiv preprint arXiv:2503.09115, 2025. doi:10.48550/arXiv.2503.09115.

[bib.bib3] [3] Pankaj K. Agarwal, Noga Alon, Boris Aronov, and Subash Suri. Can visibility graphs be represented compactly? Discrete Comput. Geom., 12(3):347–365, 1994. doi:10.1007/BF02574385.

[bib.bib4] [4] Pankaj K. Agarwal, Boris Aronov, Esther Ezra, Matthew J. Katz, and Micha Sharir. Intersection queries for flat semi-algebraic objects in three dimensions and related problems. In Xavier Goaoc and Michael Kerber, editors, 38th International Symposium on Computational Geometry, SoCG 2022, June 7-10, 2022, Berlin, Germany, volume 224 of LIPIcs, pages 4:1–4:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPICS.SOCG.2022.4.

[bib.bib5] [5] Pankaj K. Agarwal, Boris Aronov, Esther Ezra, Matthew J. Katz, and Micha Sharir. Intersection queries for flat semi-algebraic objects in three dimensions and related problems. arXiv preprint 2203.10241, 2025. doi:10.48550/arXiv.2203.10241.

[bib.bib6] [6] Pankaj K. Agarwal and Jeff Erickson. Geometric range searching and its relatives. Contemporary Mathematics, 223(1):56, 1999. doi:10.1090/conm/223/03131.

[bib.bib7] [7] Pankaj K. Agarwal, Esther Ezra, and Micha Sharir. Semi-algebraic off-line range searching and biclique partitions in the plane. In Wolfgang Mulzer and Jeff M. Phillips, editors, 40th International Symposium on Computational Geometry, SoCG 2024, June 11-14, 2024, Athens, Greece, volume 293 of LIPIcs, pages 4:1–4:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPICS.SOCG.2024.4.

[bib.bib8] [8] Pankaj K. Agarwal and Kasturi R. Varadarajan. Efficient algorithms for approximating polygonal chains. Discrete Comput. Geom., 23(2):273–291, 2000. doi:10.1007/PL00009500.

[bib.bib9] [9] Adeli A. Ahmadlou M., Adeli H. New diagnostic EEG markers of the Alzheimer’s disease using visibility graph. J. Neural Transm., 117:1099–1109, 2010. doi:10.1007/s00702-010-0450-3.

[bib.bib10] [10] Noga Alon, János Pach, Rom Pinchasi, Radoš Radoičić, and Micha Sharir. Crossing patterns of semi-algebraic sets. J. Combin. Theory Ser. A, 111(2):310–326, 2005. doi:10.1016/j.jcta.2004.12.008.

[bib.bib11] [11] Safwa Ameer, Matt Gibson-Lopez, Erik Krohn, Sean Soderman, and Qing Wang. Terrain visibility graphs: persistence is not enough. In 36th International Symposium on Computational Geometry, volume 164 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 6, 13. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020. doi:10.4230/LIPICS.SOCG.2020.6.

[bib.bib12] [12] Stav Ashur, Omrit Filtser, Matthew J. Katz, and Rachel Saban. Terrain-like graphs: PTASs for guarding weakly-visible polygons and terrains. Comput. Geom., 101:Paper No. 101832, 13, 2022. doi:10.1016/j.comgeo.2021.101832.

[bib.bib13] [13] Abdul Basit, Artem Chernikov, Sergei Starchenko, Terence Tao, and Chieu-Minh Tran. Zarankiewicz’s problem for semilinear hypergraphs. In Forum of Mathematics, Sigma, volume 9, page e59. Cambridge University Press, 2021. doi:10.1017/fms.2021.52.

[bib.bib14] [14] Sujoy Bhore, Timothy M. Chan, Zhengcheng Huang, Shakhar Smorodinsky, and Csaba D. Tóth. Sparse bounded hop-spanners for geometric intersection graphs. arXiv preprint arXiv:2504.05861, 2025. doi:10.48550/arXiv.2504.05861.

[bib.bib15] [15] Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. Twin-width I: tractable fo model checking. ACM Journal of the ACM (JACM), 69(1):1–46, 2021. doi:10.1145/3486655.

[bib.bib16] [16] Andreas Brandstädt, Van Bang Le, and Jeremy P. Spinrad. Graph classes: a survey. SIAM Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1999. doi:10.1137/1.9780898719796.

[bib.bib17] [17] Peter Braß and Christian Knauer. On counting point-hyperplane incidences. Computational Geometry, 25(1-2):13–20, 2003. doi:10.1016/S0925-7721(02)00127-X.

[bib.bib18] [18] Sergio Cabello, Siu-Wing Cheng, Otfried Cheong, and Christian Knauer. Geometric matching and bottleneck problems. In 40th International Symposium on Computational Geometry, SoCG 2024, June 11-14, 2024, Athens, Greece, pages 31:1–31:15, 2024. doi:10.4230/LIPICS.SOCG.2024.31.

[bib.bib19] [19] Jean Cardinal and Micha Sharir. Improved algebraic degeneracy testing. Discrete & Computational Geometry, pages 1–19, 2024. doi:10.1007/s00454-024-00673-7.

[bib.bib20] [20] Jean Cardinal and Yelena Yuditsky. Compact representation of semilinear and terrain-like graphs. arXiv preprint arXiv:2507.00252, 2025. doi:10.48550/arXiv.2507.00252.

[bib.bib21] [21] Timothy M. Chan. Dynamic subgraph connectivity with geometric applications. SIAM Journal on Computing, 36(3):681–694, 2006. doi:10.1137/S009753970343912X.

[bib.bib22] [22] Timothy M. Chan. All-pairs shortest paths with real weights in $O(n^{3}/\log n)$ Time. Algorithmica, 50(2):236–243, 2008. doi:10.1007/S00453-007-9062-1.

[bib.bib23] [23] Timothy M. Chan. Optimal partition trees. Discrete Comput. Geom., 47(4):661–690, 2012. doi:10.1007/s00454-012-9410-z.

[bib.bib24] [24] Timothy M Chan, Pingan Cheng, and Da Wei Zheng. Semialgebraic range stabbing, ray shooting, and intersection counting in the plane. In 40th International Symposium on Computational Geometry, SoCG 2024, page 33. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, 2024. doi:10.4230/LIPIcs.SoCG.2024.33.

[bib.bib25] [25] Timothy M. Chan and Dimitrios Skrepetos. All-pairs shortest paths in geometric intersection graphs. J. Comput. Geom., 10(1):27–41, 2019. doi:10.20382/JOCG.V10I1A2.

[bib.bib26] [26] Bernard Chazelle. Cutting hyperplanes for divide-and-conquer. Discrete Comput. Geom., 9(2):145–158, 1993. doi:10.1007/BF02189314.

[bib.bib27] [27] Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas, and Micha Sharir. Algorithms for bichromatic line-segment problems polyhedral terrains. Algorithmica, 11(2):116–132, 1994. doi:10.1007/BF01182771.

[bib.bib28] [28] Bernard Chazelle and Leonidas J. Guibas. Visibility and intersection problems in plane geometry. Discret. Comput. Geom., 4:551–581, 1989. doi:10.1007/BF02187747.

[bib.bib29] [29] Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva. Maximum flow and minimum-cost flow in almost-linear time. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022, pages 612–623. IEEE, 2022. doi:10.1109/FOCS54457.2022.00064.

[bib.bib30] [30] Fan R. K. Chung, Paul Erdős, and Joel Spencer. On the decomposition of graphs into complete bipartite subgraphs. In Studies in pure mathematics, pages 95–101. Birkhäuser, Basel, 1983. doi:10.1007/978-3-0348-5438-2_10.

[bib.bib31] [31] David Conlon. Some remarks on the Zarankiewicz problem. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 173(1), pages 155–161. Cambridge University Press, 2022. doi:10.1017/S0305004121000475.

[bib.bib32] [32] David Conlon, Jacob Fox, János Pach, Benny Sudakov, and Andrew Suk. Ramsey-type results for semi-algebraic relations. Trans. Amer. Math. Soc., 366(9):5043–5065, 2014. doi:10.1090/S0002-9947-2014-06179-5.

[bib.bib33] [33] Jonathan B. Conroy and Csaba D. Tóth. Hop-spanners for geometric intersection graphs. J. Comput. Geom., 14(2):26–64, 2022. doi:10.20382/JOCG.V14I2A3.

[bib.bib34] [34] James Davies, Tomasz Krawczyk, Rose McCarty, and Bartosz Walczak. Coloring polygon visibility graphs and their generalizations. J. Combin. Theory Ser. B, 161:268–300, 2023. doi:10.1016/j.jctb.2023.02.010.

[bib.bib35] [35] Mark de Berg, Otfried Cheong, Marc J. van Kreveld, and Mark H. Overmars. Computational geometry: algorithms and applications, 3rd Edition. Springer, 2008. doi:10.1007/978-3-540-77974-2.

[bib.bib36] [36] Sarita de Berg, Nathan van Beusekom, Max van Mulken, Kevin Verbeek, and Jules Wulms. Competitive searching over terrains. In José A. Soto and Andreas Wiese, editors, LATIN 2024: Theoretical Informatics - 16th Latin American Symposium, Puerto Varas, Chile, March 18-22, 2024, Proceedings, Part I, volume 14578 of Lecture Notes in Computer Science, pages 254–269. Springer, 2024. doi:10.1007/978-3-031-55598-5_17.

[bib.bib37] [37] Thao Do. Representation complexities of semialgebraic graphs. SIAM J. Discrete Math., 33(4):1864–1877, 2019. doi:10.1137/18M1221606.

[bib.bib38] [38] Herbert Edelsbrunner. Algorithms in combinatorial geometry, volume 10 of EATCS Monographs on Theoretical Computer Science. Springer-Verlag, Berlin, 1987. doi:10.1007/978-3-642-61568-9.

[bib.bib39] [39] Jeff Erickson. New lower bounds for Hopcroft’s problem. Discrete & Computational Geometry, 16(4):389–418, 1996. doi:10.1007/BF02712875.

[bib.bib40] [40] William Evans and Noushin Saeedi. On characterizing terrain visibility graphs. J. Comput. Geom., 6(1):108–141, 2015. doi:10.20382/jocg.v6i1a5.

[bib.bib41] [41] Tomás Feder and Rajeev Motwani. Clique partitions, graph compression and speeding-up algorithms. J. Comput. System Sci., 51(2):261–272, 1995. doi:10.1006/jcss.1995.1065.

[bib.bib42] [42] Jacob Fox, János Pach, Adam Sheffer, Andrew Suk, and Joshua Zahl. A semi-algebraic version of Zarankiewicz’s problem. J. Eur. Math. Soc. (JEMS), 19(6):1785–1810, 2017. doi:10.4171/JEMS/705.

[bib.bib43] [43] Vincent Froese and Malte Renken. A fast shortest path algorithm on terrain-like graphs. Discrete Comput. Geom., 66(2):737–750, 2021. doi:10.1007/s00454-020-00226-8.

[bib.bib44] [44] Vincent Froese and Malte Renken. Persistent graphs and cyclic polytope triangulations. Comb., 41(3):407–423, 2021. doi:10.1007/S00493-020-4369-5.

[bib.bib45] [45] Vincent Froese and Malte Renken. Terrain-like graphs and the median Genocchi numbers. European J. Combin., 115:Paper No. 103780, 8, 2024. doi:10.1016/j.ejc.2023.103780.

[bib.bib46] [46] Subir K. Ghosh. Visibility Algorithms in the Plane. Cambridge University Press, 2007. doi:10.1017/CBO9780511543340.

[bib.bib47] [47] Oktay Günlük. A new min-cut max-flow ratio for multicommodity flows. SIAM Journal on Discrete Mathematics, 21(1):1–15, 2007. doi:10.1137/S089548010138917X.

[bib.bib48] [48] Larry Guth and Nets Hawk Katz. On the Erdős distinct distances problem in the plane. Ann. of Math. (2), 181(1):155–190, 2015. doi:10.4007/annals.2015.181.1.2.

[bib.bib49] [49] Pavol Hell, Jing Huang, Jephian C.-H. Lin, and Ross M. McConnell. Bipartite analogues of comparability and cocomparability graphs. SIAM J. Discrete Math., 34(3):1969–1983, 2020. doi:10.1137/19M1263789.

[bib.bib50] [50] Jing Huang. Representation characterizations of chordal bipartite graphs. J. Combin. Theory Ser. B, 96(5):673–683, 2006. doi:10.1016/j.jctb.2006.01.001.

[bib.bib51] [51] Stasys Jukna and Alexander S Kulikov. On covering graphs by complete bipartite subgraphs. Discrete Mathematics, 309(10):3399–3403, 2009. doi:10.1016/J.DISC.2008.09.036.

[bib.bib52] [52] Prahlad Narasimhan Kasthurirangan. One-sided terrain guarding and chordal graphs. Discrete Appl. Math., 348:192–201, 2024. doi:10.1016/j.dam.2024.01.034.

[bib.bib53] [53] Matthew J. Katz, Rachel Saban, and Micha Sharir. Near-linear algorithms for visibility graphs over a 1.5-dimensional terrain. In Timothy Chan, Johannes Fischer, John Iacono, and Grzegorz Herman, editors, 32nd Annual European Symposium on Algorithms (ESA 2024), volume 308 of Leibniz International Proceedings in Informatics (LIPIcs), pages 77:1–77:17, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ESA.2024.77.

[bib.bib54] [54] Matthew J. Katz and Micha Sharir. An expander-based approach to geometric optimization. SIAM J. Comput., 26(5):1384–1408, 1997. doi:10.1137/S0097539794268649.

[bib.bib55] [55] Oliver Kullmann and Ankit Shukla. Transforming quantified boolean formulas using biclique covers. In International Conference on Tools and Algorithms for the Construction and Analysis of Systems, pages 372–390. Springer, 2023. doi:10.1007/978-3-031-30820-8_23.

[bib.bib56] [56] Lucas Lacasa, Bartolo Luque, Fernando Ballesteros, Jordi Luque, and Juan Carlos Nuño. From time series to complex networks: The visibility graph. Proceedings of the National Academy of Sciences, 105(13):4972–4975, 2008. doi:10.1073/pnas.0709247105.

[bib.bib57] [57] Jiří Matoušek. Range searching with efficient hierarchical cuttings. In Proceedings of the eighth annual symposium on Computational geometry, pages 276–285, 1992. doi:10.1145/142675.142732.

[bib.bib58] [58] Jiří Matoušek. Cutting hyperplane arrangements. Discrete Comput. Geom., 6(5):385–406, 1991. doi:10.1007/BF02574697.

[bib.bib59] [59] Jiří Matoušek. Efficient partition trees. Discrete Comput. Geom., 8(3):315–334, 1992. ACM Symposium on Computational Geometry (North Conway, NH, 1991). doi:10.1007/BF02293051.

[bib.bib60] [60] Jiří Matoušek. Range searching with efficient hierarchical cuttings. Discrete Comput. Geom., 10(2):157–182, 1993. doi:10.1007/BF02573972.

[bib.bib61] [61] Jiří Matoušek and Zuzana Patáková. Multilevel polynomial partitions and simplified range searching. Discrete Comput. Geom., 54(1):22–41, 2015. doi:10.1007/s00454-015-9701-2.

[bib.bib62] [62] Joseph O’Rourke. Visibility. In Handbook of Discrete and Computational Geometry, 3rd Edition, chapter 33. Chapman and Hall/CRC, 2017. doi:10.1201/9781420035315.CH28.

[bib.bib63] [63] János Pach and Micha Sharir. Incidences. In Graph theory, combinatorics and algorithms, pages 267–292. Springer, New York, 2005. doi:10.1007/0-387-25036-0_11.

[bib.bib64] [64] Larry Palazzi and Jack Snoeyink. Counting and reporting red/blue segment intersections. CVGIP: Graphical Models and Image Processing, 56(4):304–310, 1994. doi:10.1006/cgip.1994.1027.

[bib.bib65] [65] Franco P. Preparata and Michael Ian Shamos. Computational geometry. Texts and Monographs in Computer Science. Springer-Verlag, New York, 1985. doi:10.1007/978-1-4612-1098-6.

[bib.bib66] [66] Vojtech Rödl and Andrzej Ruciński. Bipartite coverings of graphs. Combinatorics, Probability and Computing, 6(3):349–352, 1997. doi:10.1017/S0963548397003064.

[bib.bib67] [67] Lisa Sauermann. On the speed of algebraically defined graph classes. Advances in Mathematics, 380:107593, 2021. doi:10.1016/j.aim.2021.107593.

[bib.bib68] [68] Stephan Schwartz. An overview of graph covering and partitioning. Discrete Math., 345(8):Paper No. 112884, 17, 2022. doi:10.1016/j.disc.2022.112884.

[bib.bib69] [69] Anish Man Singh Shrestha, Satoshi Tayu, and Shuichi Ueno. On orthogonal ray graphs. Discrete Appl. Math., 158(15):1650–1659, 2010. doi:10.1016/j.dam.2010.06.002.

[bib.bib70] [70] Shakhar Smorodinsky. A survey of Zarankiewicz problems in geometry. arXiv preprint arXiv:2410.03702, 2024. doi:10.48550/arXiv.2410.03702.

[bib.bib71] [71] Andrew Suk. Semi-algebraic Ramsey numbers. J. Combin. Theory Ser. B, 116:465–483, 2016. doi:10.1016/j.jctb.2015.10.001.

[bib.bib72] [72] Xiaoying Tang, Li Xia, Yezi Liao, Weifeng Liu, Yuhua Peng, Tianxin Gao, and Yanjun Zeng. New approach to epileptic diagnosis using visibility graph of high-frequency signal. Clinical EEG and Neuroscience, 44(2):150–156, 2013. PMID: 23508995. doi:10.1177/1550059412464449.

[bib.bib73] [73] István Tomon. Ramsey properties of semilinear graphs. Israel Journal of Mathematics, 254(1):113–139, 2023. doi:10.1007/s11856-022-2390-7.

[bib.bib74] [74] Csaba D. Tóth. Weighted biclique covers. Open problem posed at the Tenth Annual Workshop on Geometry and Graphs (WoGaG’23), Bellairs Research Institute, 2023.

[bib.bib75] [75] Zsolt Tuza. Covering of graphs by complete bipartite subgraphs: complexity of $0$ - $1$ matrices. Combinatorica, 4(1):111–116, 1984. doi:10.1007/BF02579163.

[bib.bib76] [76] Jan van den Brand, Li Chen, Richard Peng, Rasmus Kyng, Yang P. Liu, Maximilian Probst Gutenberg, Sushant Sachdeva, and Aaron Sidford. A deterministic almost-linear time algorithm for minimum-cost flow. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023, pages 503–514. IEEE, 2023. doi:10.1109/FOCS57990.2023.00037.

[bib.bib77] [77] Peter van Emde Boas. Preserving order in a forest in less than logarithmic time. In 16th Annual Symposium on Foundations of Computer Science (Univ. California, Berkeley, Calif., 1975), pages 75–84. IEEE, Long Beach, CA, 1975. doi:10.1109/SFCS.1975.26.

Compact Representation of Semilinear and Terrain-Like Graphs

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

1.1 Our results

1.2 Background

1.2.1 Covers and partitions in general graphs

Theorem 1 ([30, 75]).

Observation 2.

Observation 3.

1.2.2 Algorithms

Lemma 4 ([41]).

Lemma 5 ([18]).

1.2.3 Spanners

Lemma 6 ([33]).

1.2.4 Biclique covers and range searching

Theorem 7 ([37, 5]).

1.2.5 Ordered graphs and visibility graphs

1.3 Plan of the paper

2 𝒅-dimensional comparability graphs

Theorem 8.

Proof.

Theorem 9.

3 Semilinear graphs

Theorem 10.

Proof.

Corollary 11 ([13]).

Lemma 12.

Theorem 13.

4 Terrain-like graphs

Lemma 14.

Proof.

Theorem 15.

Proof.

Lemma 16.

Proof.

Theorem 17.

5 Lower bounds

Lemma 18.

Proof.

Claim 19.

Proof of claim..

Lemma 20.

Proof.

Lemma 21.

Proof.

6 Open questions

References

2 $𝒅$ -dimensional comparability graphs