Pith. sign in

REVIEW 3 major objections 4 minor 84 references

Compact Representation of Semilinear and Terrain-like Graphs

T0 review · 3 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Semilinear graphs of constant complexity have biclique covers of size $O(n \operatorname{polylog} n)$; capped graphs get $O(n \log^3 n)$; some unit disk graphs force $\Omega(n^{4/3})$.

desk verdict Strong upper-bound paper with a lower-bound section that doesn't hold up as written; the semilinear and terrain-like results are worth refereeing, the unit-disk claim needs real work. read the letter →

arxiv 2507.00252 v1 pith:FVR7IAFE submitted 2025-06-30 math.CO cs.CGcs.DM

Jean Cardinal , Yelena Yuditsky This is my paper · ORCID
classification math.COcs.CGcs.DM MSC 05C7005C6205C35
keywords bicliquecoverpartitionsemilineargraphcomparabilitybigraphcappedterrain-likevisibilityunitdisk
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Graphs can be stored compactly by covering their edges with complete bipartite subgraphs, where the cost is the total number of vertices over all bicliques; small covers make matching, shortest paths, and spanners faster. The paper's main theorem says every semilinear graph of constant complexity—any graph whose edges are decided by a fixed set of linear inequalities in a fixed dimension—admits a biclique cover of size $O(n \operatorname{polylog} n)$. This single statement generalizes earlier near-linear covers for interval graphs, permutation graphs, bounded-boxicity graphs, and L-shape intersection graphs, and it implies the known semilinear Zarankiewicz bound. The paper also gives an elementary proof that capped (terrain-like) ordered graphs admit biclique partitions of size $O(n \log^3 n)$, a combinatorial analogue of the classical compact-representation result for polygon visibility graphs. Finally, it constructs unit disk graphs whose biclique covers all have size $\Omega(n^{4/3})$, answering a question about whether such graphs could have near-linear covers.

What carries the argument

The central object is the biclique cover (or partition) of a graph, sized as the sum of $|V(H)|$ over the bicliques $H$. The mechanism that carries the semilinear-graph argument is the $d$-dimensional comparability bigraph: points in $\mathbb{R}^d$ with an edge from left to right when one $d$-tuple is coordinate-wise smaller than the other. Each conjunction of linear inequalities is rewritten as such a dominance condition, and Theorem 6 partitions any $d$-dimensional comparability bigraph in $O(n \log^d n)$ by splitting along one coordinate and recursing. For capped graphs, the key lemma identifies every capped bigraph with a two-dimensional comparability bigraph by assigning each vertex coordinates that encode its first and last neighbours, turning the forbidden-pattern condition into a dominance test.

What would settle it

Take the standard tight point-line configurations on $n$ points and $n$ lines, shift the lines upward slightly, replace them by very large circles, and scale to unit disks; if any biclique cover of the resulting unit disk graph had size $o(n^{4/3})$, the lower-bound claim would be wrong. On the upper-bound side, the decisive check is the quoted reduction: prove or disprove that every constant-complexity semilinear graph is dnf-semilinear with both the number of clauses and the number of linear functions per clause depending only on the original complexity.

Watch

Extended reading notes

Core claim

On its own terms, the paper establishes that semilinear graphs of constant complexity are a class of geometric graphs that can be compressed: every such graph on $n$ vertices has a biclique cover of size $O(n \operatorname{polylog} n)$. The proof routes through dnf-semilinear forms: a conjunction of linear inequalities $f_{i,j}(x,y)<0$ is rewritten as $g_i(x) \prec -h_i(y)$, so across any split of the vertex set the edges form two $t$-dimensional comparability bigraphs, and the recursive construction of Theorem 6 partitions each in $O(n \log^t n)$. For capped graphs, the paper shows every capped bigraph is a two-dimensional comparability bigraph and then applies the same recursion, yielding an $O(n \log^3 n)$ biclique partition. On the lower-bound side, it shows that incidence graphs of points and closed lower halfplanes, and hence unit disk graphs, can require biclique covers of size $\Omega(n^{4/3})$, so near-linear covers cannot be expected once defining functions are allowed to be quadratic.

Load-bearing premise

The semilinear-graph theorem rests on a cited result that every semilinear graph of constant complexity can be rewritten in disjunctive normal form with constants depending only on the original complexity; the paper quotes this result without proving it or stating the parameter bounds.

Editorial extensions

If this is right

  • Corollary 9 follows directly: every $K_{t,t}$-free semilinear graph of constant complexity has $O(n \operatorname{polylog} n)$ edges, recovering the Zarankiewicz bound of [14].
  • Every semilinear graph has a 3-hop spanner with $O(n \operatorname{polylog} n)$ edges, by Lemma 4 applied to the cover.
  • For semilinear graphs, the cover can be computed in $O(n \operatorname{polylog} n)$ time, so maximum matching runs in $O(n^{1+\varepsilon})$ and all-pairs shortest paths in $O(n^2 \operatorname{polylog} n)$.
  • Every capped graph has a biclique partition of size $O(n \log^3 n)$, computable in $O(\max\{|E|, n \log^3 n\})$ time from sorted adjacency lists, giving a BFS tree in $O(n \log^3 n)$ per root after preprocessing.
  • There are unit disk graphs on $n$ vertices with no biclique cover of size $o(n^{4/3})$, so near-linear covers cannot be expected for semialgebraic graphs of degree two.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Because the semilinear proof is constructive, the same argument likely yields fast approximation algorithms for geometric intersection graphs beyond the classes explicitly named; this is an extrapolation, not a paper claim.
  • The unit-disk lower bound suggests a degree threshold: near-linear biclique covers are possible when all defining functions are linear, while quadratic functions already force $\Omega(n^{4/3})$-size covers; the paper states a similar expectation for translates of smooth strictly convex bodies.
  • The identification of capped bigraphs with two-dimensional comparability bigraphs is likely to transfer algorithmic machinery from permutation graphs to terrain-visibility problems; the paper leaves this transfer implicit.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper studies biclique covers of graphs, where size is the sum of the vertex counts of the bicliques. It surveys classical and recent results and contributes new upper bounds: semilinear graphs of constant complexity admit biclique covers of size O(n polylog n), terrain-like (capped) graphs admit partitions of size O(n log^3 n), and several restricted classes (grounded L-shapes, x-grounded L-shapes, grid graphs, interval graphs, bounded-boxicity graphs, bichromatic segment intersection graphs) receive improved or matching bounds. It also claims a lower bound: some unit disk graphs require biclique covers of size Ω(n^{4/3}), answering a question of Tóth. The upper-bound arguments are largely self-contained, while the lower-bound section relies on a point-halfplane incidence construction and a reduction to unit disks.

Significance. If the upper-bound results stand, they provide a clean unifying framework for many previously scattered results and give new algorithmic implications via known reductions to matching and shortest paths. The proofs of Theorems 6, 8, 13, 16, 17, 21, 22, and 24 are elegant and mostly self-contained, with only standard external tools (Szemerédi-Trotter, Tomon's DNF equivalence). The claimed lower bound for unit disk graphs would be a significant negative answer to Tóth's question and would delineate the boundary between semilinear and semialgebraic graphs. However, the lower-bound section as written contains serious gaps that leave the central negative result unproved.

major comments (3)
  1. [Section 6, Lemma 26, Claim 1] The proof of Claim 1 is incorrect as stated. The claimed dichotomy "either p is incident to only one line, or ℓ contains only one point" is false. For example, take the two lines y=0 and y=x with P={(0,0),(1,0)}. The point p=(0,0) is incident to both lines, yet the line y=0 contains another point of P, and all points lie in the intersection of the two closed lower halfplanes. Thus the leftmost-incidence argument does not go through. Since the intended induction (attributed to Erickson [43]) is not supplied, the claimed bound ι(Pi,Li) ≤ |Pi|+|Li| is unsupported, and consequently the Ω(n^{4/3}) lower bound for point-halfplane incidence graphs is not established.
  2. [Section 6, Lemma 27] The reduction from point-halfplane incidences to unit disk intersection graphs is not rigorous. The proof shifts lines upward and replaces them by circles of very large radius, but it gives no quantitative estimates. A unit disk tangent to a line contains points only below a parabola; to realize the incidences exactly, one needs a spread-separation tradeoff of the form R ≳ D^2/δ, where D is the global diameter and δ the minimum separation between points and non-incident lines. The proof provides no construction or error control, so the claimed realization of I(P,H) as a unit disk graph is not established. Since this lemma is the basis for the negative answer to Tóth's question, the central lower-bound result is unproved.
  3. [Section 3, proof of Theorem 8] The proof relies on the statement that every semilinear graph of complexity t is dnf-semilinear of complexity (t',ℓ) with t' and ℓ depending only on t, attributed to Tomon [79] without proof or parameter bounds. Because this equivalence is load-bearing for the reduction to comparability bigraphs, the paper should either provide a proof, state the precise parameter dependence, or cite a specific theorem with full statement. As written, a reader cannot verify that the O(n polylog n) bound follows from the given definition of complexity.
minor comments (4)
  1. [Section 2, proof of Theorem 6] There is a typo: "let R′ ⊆ R be the of vertices r ∈ R" should read "let R′ ⊆ R be the set of vertices r ∈ R".
  2. [Section 5.5, proof of Theorem 24] In the definition of Sb_1 and Sb_2, the text says "short red intervals in Sb_v", but Sb_v is the blue short list; these should be "short blue intervals".
  3. [Section 5.4, Theorem 22] The phrase "This improves on results by Tomon and Zakharov [80] and Basit et al. [14] by a factor log^d n" is imprecise: those works give different bounds (polylog factors in the Zarankiewicz context), and the comparison should be stated more carefully to avoid implying a direct improvement in the same parameter.
  4. [Section 6, Lemma 26] The notation I(P,H) is used for the incidence graph of points and halfplanes, but the proof then refers to ι(P,L) for lines; the relationship between the halfplanes H and the set of lines L should be made explicit to avoid confusion.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main theorems are proved from scratch by reductions to comparability bigraphs; cited external results are genuine independent inputs, and the only self-citation is a background reference with no load-bearing role.

full rationale

The paper's central upper bounds (Theorems 6, 7, 8, 13, 16, 17, 21, 22, 24, and 25) are derived by self-contained induction and divide-and-conquer arguments. Theorem 8 reduces semilinear graphs to biclique covers of d-dimensional comparability bigraphs, with the DNF normalization imported from Tomon [79]; that is an external mathematical result, not the authors' own claim, and it is not defined in terms of biclique covers, so no circularity arises even though the paper gives no proof of it. Theorem 13 and the L-shape results reduce capped/bigraph classes to 2-dimensional comparability bigraphs with an explicit embedding (Lemma 12). The lower-bound section (Lemmas 26-27) is not circular: Lemma 26 proves an incidence-counting claim via a charging argument (though the written proof of Claim 1 is questionable, and the subsequent unit-disk realization lacks quantitative error estimates, which is a correctness or rigor issue rather than a self-definitional one), and Lemma 27 reduces unit-disk graphs to the incidence graph by a geometric construction. The single self-citation, [21] (Cardinal and Sharir), appears only in a background list of polynomial-partitioning references and plays no role in any proof. No fitted parameter is renamed as a prediction, no uniqueness theorem is imported from the authors' previous work, and no known result is merely renamed. These observations also flag the paper's own tacit reliance on an unproved external statement in Section 3, but that is an assumption gap, not circularity.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central upper-bound theorems are proved from first principles apart from (i) the cited DNF reduction for semilinear graphs, (ii) the known Szemerédi-Trotter tight constructions used only in the lower-bound section, and (iii) two cited structural results used for corollaries. No free parameters are fitted and no new entities are introduced.

assumptions (4)
  • domain assumption Existence of n point-line configurations with Θ(n^{4/3}) incidences (tight examples for Szemerédi-Trotter)
    Used as the base configuration in Lemma 26 and Lemma 27 for the lower bounds; cited to Edelsbrunner [42] and not proved in the paper.
  • domain assumption Every semilinear graph of complexity t can be written as dnf-semilinear of complexity (t', l) with t', l depending only on t (Tomon [79])
    Invoked in Section 3 before Theorem 8; the entire semilinear upper-bound proof is built on this reduction.
  • domain assumption Grid intersection graphs are 4-dimensional comparability graphs (Chaplick et al. [29], Proposition 6)
    Used in Corollary 19 to derive the near-linear biclique cover bound for grid intersection graphs.
  • domain assumption Intersection graphs of n boxes in dimension d can require Ω(n(log n / log log n)^{d-2}) edges in any 3-hop spanner (Bhore et al. [15])
    Used in Lemma 28 to transfer a spanner lower bound to a biclique cover lower bound for bounded-boxicity graphs.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Compact Representation of Semilinear and Terrain-like Graphs." pith.science (2026). https://pith.science/paper/FVR7IAFE

@misc{pith2026250700252,
  author       = {Pith},
  title        = {Pith review of: Compact Representation of Semilinear and Terrain-like Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FVR7IAFE}},
  note         = {Machine review of arXiv:2507.00252}
}
abstract

We consider the existence and construction of \textit{biclique covers} of graphs, consisting of coverings of their edge sets by complete bipartite graphs. The \textit{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)$. 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 (\textit{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 (\textit{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\'edi-Trotter type incidence bounds for higher-degree semialgebraic graphs.

Figures

Figures reproduced from arXiv: 2507.00252 by the authors.

Figure 1
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… view at source ↗
Figure 2
Figure 2. The forbidden ordered subgraph in a capped graph. The dashed curve represents a non-edge: If ik and jℓ are edges, then iℓ must be an edge. 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 < ℓ along the terrain such that there is a line of sight between i and k and between j and ℓ, then there must be one between i and ℓ. In fac… view at source ↗
Figure 3
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 ik such that k ≥ i + 2, there exists j such that i < j < k and both ij and jk are also edges [12, 48]. It is known that terrain visibility graphs are also persistent,… view at source ↗
Figures from the paper (6 more)
Figure 4
Figure 4. Figure 4: Comparability graphs and bigraphs. comparability graph could have small biclique covers. A simple counting argument rules this out: all bipartite graphs are comparability graphs, and there are 2Ω(n 2 ) bipartite graphs on n vertices. From Observation 2, there must exis…
Figure 5
Figure 5. Figure 5: Illustration of the proof of Lemma 12. The proof is illustrated in [PITH_FULL_IMAGE:figures/full_fig_p011_5.png]
Figure 6
Figure 6. Figure 6: The forbidden ordered subgraph in an intersection graph of grounded L-shapes. The dashed curve represents a non-edge: If ik and jℓ are edges, then jk must be an edge. It turns out that we can apply the exact same strategy as we do for capped graphs in the proof of Theo…
Figure 7
Figure 7. Figure 7: An intersection graph of grounded L-shapes. The bipartite intersection graphs of these horizontal and vertical segments is a two-directional orthogonal ray graph in which two segments intersect if and only if the corresponding L-shapes intersect. Hence the intersection…
Figure 8
Figure 8. Figure 8: An intersection graph of x-grounded L-shapes. The set of red shapes is A1 and the set of blue shapes is B1. is a two-dimensional comparability bigraph. By Theorem 6 each one of them, and therefore their union, has a biclique cover of size O(n log2 n). It remains to rec…
Figure 9
Figure 9. Figure 9: The slab corresponding to v with long blue segments L b v and red short segments S r 1 which intersect the left boundary of the slab. It is possible to extend the segments in S r 1 such that they intersect the right boundary of the slab corresponding to v and the inter…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

84 extracted references · 79 canonical work pages

  1. [43]

    New lower bounds for Hopcroft’s problem

    Jeff Erickson. New lower bounds for Hopcroft’s problem. Discrete & Computational Geometry, 16(4):389–418, 1996

    work page 1996

  2. [79]

    Ramsey properties of semilinear graphs

    Istv´ an Tomon. Ramsey properties of semilinear graphs. Israel Journal of Mathematics , 254(1):113–139, 2023

    work page 2023

  3. [1]

    Visibility graphs of staircase polygons and the weak Bruhat order

    James Abello, ¨Omer E˘ gecio˘ glu, 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

    1995

  4. [2]

    The Zarankiewicz Problem for Polygon Visibility Graphs

    Eyal Ackerman and Bal´ azs Keszegh. The Zarankiewicz Problem for Polygon Visibility Graphs. arXiv preprint arXiv:2503.09115 , 2025

    work page arXiv 2025

  5. [3]

    Agarwal, Noga Alon, Boris Aronov, and Subash Suri

    Pankaj K. Agarwal, Noga Alon, Boris Aronov, and Subash Suri. Can visibility graphs be represented compactly? Discrete Comput. Geom., 12(3):347–365, 1994

    1994

  6. [4]

    Agarwal, Boris Aronov, Esther Ezra, Matthew J

    Pankaj K. Agarwal, Boris Aronov, Esther Ezra, Matthew J. Katz, and Micha Sharir. Inter- section 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–...

    2022

  7. [5]

    Intersection Queries for Flat Semi-Algebraic Objects in Three Dimensions and Related Problems

    Pankaj K. Agarwal, Boris Aronov, Esther Ezra, Matthew J. Katz, and Micha Sharir. Inter- section queries for flat semi-algebraic objects in three dimensions and related problems. arXiv preprint 2203.10241, 2025

    work page Pith review arXiv 2025

  8. [6]

    Agarwal and Jeff Erickson

    Pankaj K. Agarwal and Jeff Erickson. Geometric range searching and its relatives. Contem- porary Mathematics, 223(1):56, 1999

    1999

Show all 84 references
  1. [7]

    Agarwal, Esther Ezra, and Micha Sharir

    Pankaj K. Agarwal, Esther Ezra, and Micha Sharir. Semi-algebraic off-line range search- ing 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, Gree...

    2024

  2. [8]

    Agarwal and Kasturi R

    Pankaj K. Agarwal and Kasturi R. Varadarajan. Efficient algorithms for approximating polygonal chains. Discrete Comput. Geom., 23(2):273–291, 2000

    2000

  3. [9]

    Ahmadlou M., Adeli H

    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

    2010

  4. [10]

    L-graphs and monotone L-graphs

    Abu Reyan Ahmed, Felice De Luca, Sabin Devkota, Alon Efrat, Md Iqbal Hossain, Stephen Kobourov, Jixian Li, Sammi Abida Salma, and Eric Welch. L-graphs and monotone L-graphs. arXiv preprint arXiv:1703.01544 , 2017

    2017 arXiv

  5. [11]

    Crossing patterns of semi-algebraic sets

    Noga Alon, J´ anos Pach, Rom Pinchasi, Radoˇ s Radoiˇ ci´ c, and Micha Sharir. Crossing patterns of semi-algebraic sets. J. Combin. Theory Ser. A , 111(2):310–326, 2005

    2005

  6. [12]

    Terrain vis- ibility graphs: persistence is not enough

    Safwa Ameer, Matt Gibson-Lopez, Erik Krohn, Sean Soderman, and Qing Wang. Terrain vis- ibility 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 Dagstuh...

    2020

  7. [13]

    Katz, and Rachel Saban

    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

    2022

  8. [14]

    Zarankiewicz’s problem for semilinear hypergraphs

    Abdul Basit, Artem Chernikov, Sergei Starchenko, Terence Tao, and Chieu-Minh Tran. Zarankiewicz’s problem for semilinear hypergraphs. In Forum of Mathematics, Sigma , vol- ume 9, page e59. Cambridge University Press, 2021

    2021

  9. [15]

    Chan, Zhengcheng Huang, Shakhar Smorodinsky, and Csaba D

    Sujoy Bhore, Timothy M. Chan, Zhengcheng Huang, Shakhar Smorodinsky, and Csaba D. T´ oth. Sparse bounded hop-spanners for geometric intersection graphs. arXiv preprint arXiv:2504.05861, 2025

    2025 arXiv

  10. [16]

    Twin-width I: tractable fo model checking

    ´Edouard Bonnet, Eun Jung Kim, St´ ephan Thomass´ e, and R´ emi Watrigant. Twin-width I: tractable fo model checking. ACM Journal of the ACM (JACM) , 69(1):1–46, 2021. 20 JEAN CARDINAL AND YELENA YUDITSKY

    2021

  11. [17]

    Andreas Brandst ¨adt, 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

    1999

  12. [18]

    On counting point-hyperplane incidences

    Peter Braß and Christian Knauer. On counting point-hyperplane incidences. Computational Geometry, 25(1-2):13–20, 2003

    2003

  13. [19]

    Brimkov, Konstanty Junosza-Szaniawski, Sean Kafer, Jan Kratochv ´ ıl, Martin Pergel, Pawel Rzazewski, Matthew Szczepankiewicz, and Joshua Terhaar

    Valentin E. Brimkov, Konstanty Junosza-Szaniawski, Sean Kafer, Jan Kratochv ´ ıl, Martin Pergel, Pawel Rzazewski, Matthew Szczepankiewicz, and Joshua Terhaar. Homothetic poly- gons and beyond: Maximal cliques in intersection graphs. Discret. Appl. Math., 247:263–277, 2018

    2018

  14. [20]

    Geometric matching and bottleneck problems

    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

    2024

  15. [21]

    Improved algebraic degeneracy testing

    Jean Cardinal and Micha Sharir. Improved algebraic degeneracy testing. Discrete & Compu- tational Geometry, pages 1–19, 2024

    2024

  16. [22]

    Halld´ orsson, Magn´ us M

    Daniele Catanzaro, Steven Chaplick, Stefan Felsner, Bjarni V. Halld´ orsson, Magn´ us M. Halld´ orsson, Thomas Hixon, and Juraj Stacho. Max point-tolerance graphs. Discret. Appl. Math., 216:84–97, 2017

    2017

  17. [23]

    Timothy M. Chan. Dynamic subgraph connectivity with geometric applications. SIAM Journal on Computing , 36(3):681–694, 2006

    2006

  18. [24]

    Timothy M. Chan. All-pairs shortest paths with real weights in O(n3/ log n) Time. Algorith- mica, 50(2):236–243, 2008

    2008

  19. [25]

    Timothy M. Chan. Optimal partition trees. Discrete Comput. Geom., 47(4):661–690, 2012

    2012

  20. [26]

    Semialgebraic range stabbing, ray shooting, and intersection counting in the plane

    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 Com- putational Geometry, SoCG 2024 , page 33. Schloss Dagstuhl-Leibniz-Zentrum fur Informatik GmbH, Dagstuhl ...

    2024

  21. [27]

    On the number of incidences when avoiding an induced biclique in geometric settings

    Timothy M Chan and Sariel Har-Peled. On the number of incidences when avoiding an induced biclique in geometric settings. Discrete & Computational Geometry , 73(2):466–489, 2025

    2025

  22. [28]

    Chan and Dimitrios Skrepetos

    Timothy M. Chan and Dimitrios Skrepetos. All-pairs shortest paths in geometric intersection graphs. J. Comput. Geom. , 10(1):27–41, 2019

    2019

  23. [29]

    Grid intersection graphs and order dimension

    Steven Chaplick, Stefan Felsner, Udo Hoffmann, and Veit Wiechert. Grid intersection graphs and order dimension. Order, 35:363–391, 2018

    2018

  24. [30]

    Cutting hyperplanes for divide-and-conquer

    Bernard Chazelle. Cutting hyperplanes for divide-and-conquer. Discrete Comput. Geom. , 9(2):145–158, 1993

    1993

  25. [31]

    Guibas, and Micha Sharir

    Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas, and Micha Sharir. Algorithms for bichromatic line-segment problems polyhedral terrains. Algorithmica, 11(2):116–132, 1994

    1994

  26. [32]

    Bernard Chazelle and Leonidas J. Guibas. Visibility and intersection problems in plane geometry. Discret. Comput. Geom., 4:551–581, 1989

    1989

  27. [33]

    Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva

    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

  28. [34]

    Fan R. K. Chung, Paul Erd˝ os, and Joel Spencer. On the decomposition of graphs into complete bipartite subgraphs. In Studies in pure mathematics , pages 95–101. Birkh ¨auser, Basel, 1983

    1983

  29. [35]

    Some remarks on the Zarankiewicz problem

    David Conlon. Some remarks on the Zarankiewicz problem. In Mathematical Proceedings of the Cambridge Philosophical Society , volume 173, pages 155–161. Cambridge University Press, 2022

    2022

  30. [36]

    Ramsey-type results for semi-algebraic relations

    David Conlon, Jacob Fox, J´ anos Pach, Benny Sudakov, and Andrew Suk. Ramsey-type results for semi-algebraic relations. Trans. Amer. Math. Soc. , 366(9):5043–5065, 2014

    2014

  31. [37]

    Conroy and Csaba D

    Jonathan B. Conroy and Csaba D. T´ oth. Hop-spanners for geometric intersection graphs. J. Comput. Geom., 14(2):26–64, 2022

    2022

  32. [38]

    Coloring polygon visibility graphs and their generalizations

    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. COMPACT REPRESENTATION OF SEMILINEAR AND TERRAIN-LIKE GRAPHS 21

    2023

  33. [39]

    van Kreveld, and Mark H

    Mark de Berg, Otfried Cheong, Marc J. van Kreveld, and Mark H. Overmars. Computational geometry: algorithms and applications, 3rd Edition . Springer, 2008

    2008

  34. [40]

    Competitive searching over terrains

    Sarita de Berg, Nathan van Beusekom, Max van Mulken, Kevin Verbeek, and Jules Wulms. Competitive searching over terrains. In Jos´ e A. Soto and Andreas Wiese, editors,LATIN 2024: Theoretical Informatics - 16th Latin American Symposium, Puerto Varas, Chile, March 18- 22, 2024, ...

    2024

  35. [41]

    Representation complexities of semialgebraic graphs

    Thao Do. Representation complexities of semialgebraic graphs. SIAM J. Discrete Math. , 33(4):1864–1877, 2019

    2019

  36. [42]

    Algorithms in combinatorial geometry , volume 10 of EATCS Mono- graphs on Theoretical Computer Science

    Herbert Edelsbrunner. Algorithms in combinatorial geometry , volume 10 of EATCS Mono- graphs on Theoretical Computer Science . Springer-Verlag, Berlin, 1987

    1987

  37. [44]

    On characterizing terrain visibility graphs

    William Evans and Noushin Saeedi. On characterizing terrain visibility graphs. J. Comput. Geom., 6(1):108–141, 2015

    2015

  38. [45]

    Clique partitions, graph compression and speeding-up algorithms

    Tom´ as Feder and Rajeev Motwani. Clique partitions, graph compression and speeding-up algorithms. J. Comput. System Sci. , 51(2):261–272, 1995

    1995

  39. [46]

    A semi-algebraic version of Zarankiewicz’s problem

    Jacob Fox, J´ anos 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

    2017

  40. [47]

    A fast shortest path algorithm on terrain-like graphs

    Vincent Froese and Malte Renken. A fast shortest path algorithm on terrain-like graphs. Discrete Comput. Geom., 66(2):737–750, 2021

    2021

  41. [48]

    Persistent graphs and cyclic polytope triangulations

    Vincent Froese and Malte Renken. Persistent graphs and cyclic polytope triangulations. Comb., 41(3):407–423, 2021

    2021

  42. [49]

    Terrain-like graphs and the median Genocchi numbers

    Vincent Froese and Malte Renken. Terrain-like graphs and the median Genocchi numbers. European J. Combin., 115:Paper No. 103780, 8, 2024

    2024

  43. [50]

    Subir K. Ghosh. Visibility Algorithms in the Plane . Cambridge University Press, 2007

    2007

  44. [51]

    A new min-cut max-flow ratio for multicommodity flows

    Oktay G ¨unl¨uk. A new min-cut max-flow ratio for multicommodity flows. SIAM Journal on Discrete Mathematics, 21(1):1–15, 2007

    2007

  45. [52]

    On the Erd˝ os distinct distances problem in the plane.Ann

    Larry Guth and Nets Hawk Katz. On the Erd˝ os distinct distances problem in the plane.Ann. of Math. (2) , 181(1):155–190, 2015

    2015

  46. [53]

    Lin, and Ross M

    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

    1969

  47. [54]

    Hook graphs and more: Some contributions to geometric graph theory

    Thomas Stuart Hixon. Hook graphs and more: Some contributions to geometric graph theory. Master’s thesis, Technische Universitat Berlin , 2013

    2013

  48. [55]

    Representation characterizations of chordal bipartite graphs

    Jing Huang. Representation characterizations of chordal bipartite graphs. J. Combin. Theory Ser. B , 96(5):673–683, 2006

    2006

  49. [56]

    On grounded L-graphs and their relatives

    V ´ ıt Jel ´ ınek and Martin T¨opfer. On grounded L-graphs and their relatives. Electron. J. Comb., 26(3):3, 2019

    2019

  50. [57]

    On covering graphs by complete bipartite subgraphs

    Stasys Jukna and Alexander S Kulikov. On covering graphs by complete bipartite subgraphs. Discrete Mathematics, 309(10):3399–3403, 2009

    2009

  51. [58]

    One-sided terrain guarding and chordal graphs

    Prahlad Narasimhan Kasthurirangan. One-sided terrain guarding and chordal graphs. Dis- crete Appl. Math. , 348:192–201, 2024

    2024

  52. [59]

    Katz, Rachel Saban, and Micha Sharir

    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 L...

    2024

  53. [60]

    Katz and Micha Sharir

    Matthew J. Katz and Micha Sharir. An expander-based approach to geometric optimization. SIAM J. Comput. , 26(5):1384–1408, 1997

    1997

  54. [61]

    Transforming quantified boolean formulas using biclique covers

    Oliver Kullmann and Ankit Shukla. Transforming quantified boolean formulas using biclique covers. In International Conference on Tools and Algorithms for the Construction and Anal- ysis of Systems , pages 372–390. Springer, 2023

    2023

  55. [62]

    From time series to complex networks: The visibility graph

    Lucas Lacasa, Bartolo Luque, Fernando Ballesteros, Jordi Luque, and Juan Carlos Nu˜ no. From time series to complex networks: The visibility graph. Proceedings of the National 22 JEAN CARDINAL AND YELENA YUDITSKY Academy of Sciences, 105(13):4972–4975, 2008

    2008

  56. [63]

    Range searching with efficient hierarchical cuttings

    Jiˇ r ´ ı Matouˇ sek. Range searching with efficient hierarchical cuttings. InProceedings of the eighth annual symposium on Computational geometry , pages 276–285, 1992

    1992

  57. [64]

    Cutting hyperplane arrangements.Discrete Comput

    Jiˇ r ´ ı Matouˇ sek. Cutting hyperplane arrangements.Discrete Comput. Geom. , 6(5):385–406, 1991

    1991

  58. [65]

    Efficient partition trees

    Jiˇ r ´ ı Matouˇ sek. Efficient partition trees. volume 8, pages 315–334. 1992. ACM Symposium on Computational Geometry (North Conway, NH, 1991)

    1992

  59. [66]

    Range searching with efficient hierarchical cuttings.Discrete Comput

    Jiˇ r ´ ı Matouˇ sek. Range searching with efficient hierarchical cuttings.Discrete Comput. Geom., 10(2):157–182, 1993

    1993

  60. [67]

    Multilevel polynomial partitions and simplified range searching

    Jiˇ r ´ ı Matouˇ sek and Zuzana Pat´ akov´ a. Multilevel polynomial partitions and simplified range searching. Discrete Comput. Geom., 54(1):22–41, 2015

    2015

  61. [68]

    Visibility

    Joseph O’Rourke. Visibility. In Handbook of Discrete and Computational Geometry, 3rd Edition, chapter 33. Chapman and Hall/CRC, 2017

    2017

  62. [69]

    Incidences

    J´ anos Pach and Micha Sharir. Incidences. In Graph theory, combinatorics and algorithms , pages 267–292. Springer, New York, 2005

    2005

  63. [70]

    Counting and reporting red/blue segment intersections

    Larry Palazzi and Jack Snoeyink. Counting and reporting red/blue segment intersections. CVGIP: Graphical Models and Image Processing , 56(4):304–310, 1994

    1994

  64. [71]

    Preparata and Michael Ian Shamos

    Franco P. Preparata and Michael Ian Shamos. Computational geometry . Texts and Mono- graphs in Computer Science. Springer-Verlag, New York, 1985

    1985

  65. [72]

    Bipartite coverings of graphs.Combinatorics, Probability and Computing , 6(3):349–352, 1997

    Vojtech R ¨odl and Andrzej Ruci´ nski. Bipartite coverings of graphs.Combinatorics, Probability and Computing , 6(3):349–352, 1997

    1997

  66. [73]

    On the speed of algebraically defined graph classes

    Lisa Sauermann. On the speed of algebraically defined graph classes. Advances in Mathemat- ics, 380:107593, 2021

    2021

  67. [74]

    An overview of graph covering and partitioning.Discrete Math., 345(8):Pa- per No

    Stephan Schwartz. An overview of graph covering and partitioning.Discrete Math., 345(8):Pa- per No. 112884, 17, 2022

    2022

  68. [75]

    On orthogonal ray graphs

    Anish Man Singh Shrestha, Satoshi Tayu, and Shuichi Ueno. On orthogonal ray graphs. Discrete Appl. Math. , 158(15):1650–1659, 2010

    2010

  69. [76]

    A survey of Zarankiewicz problems in geometry

    Shakhar Smorodinsky. A survey of Zarankiewicz problems in geometry. arXiv preprint arXiv:2410.03702, 2024

    2024 arXiv

  70. [77]

    Semi-algebraic Ramsey numbers

    Andrew Suk. Semi-algebraic Ramsey numbers. J. Combin. Theory Ser. B , 116:465–483, 2016

    2016

  71. [78]

    New approach to epileptic diagnosis using visibility graph of high-frequency signal

    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

    2013

  72. [80]

    Tur´ an-type results for intersection graphs of boxes

    Istv´ an Tomon and Dmitriy Zakharov. Tur´ an-type results for intersection graphs of boxes. Combin. Probab. Comput., 30(6):982–987, 2021

    2021

  73. [81]

    Csaba D. T´ oth. Weighted biclique covers. Open problem posed at the Tenth Annual Workshop on Geometry and Graphs (WoGaG’23), Bellairs Research Institute, 2023

    2023

  74. [82]

    Covering of graphs by complete bipartite subgraphs: complexity of 0-1 matrices

    Zsolt Tuza. Covering of graphs by complete bipartite subgraphs: complexity of 0-1 matrices. Combinatorica, 4(1):111–116, 1984

    1984

  75. [83]

    Liu, Maximilian Probst Gutenberg, Sushant Sachdeva, and Aaron Sidford

    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 algo- rithm for minimum-cost flow. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 20...

    2023

  76. [84]

    Preserving order in a forest in less than logarithmic time

    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. COMPACT REPRESENTATION OF SEMILINEAR AND TERRAIN-LI...

    1975

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.