pith. machine review for the scientific record. sign in

arxiv: 2602.10922 · v2 · submitted 2026-02-11 · 💻 cs.CG · cs.DM· cs.DS· math.CO

Recognition: 2 theorem links

· Lean Theorem

Implicit representations via the polynomial method

Jean Cardinal , Micha Sharir
Authors on Pith no claims yet

Pith reviewed 2026-05-16 05:49 UTC · model grok-4.3

classification 💻 cs.CG cs.DMcs.DSmath.CO
keywords semialgebraic graphsadjacency labeling schemespolynomial partitioningunit disk graphssegment intersection graphsimplicit representations
0
0 comments X

The pith

Polynomial partitioning produces adjacency labels of size O(n^{1-2/(d+1) + ε}) bits for semialgebraic graphs.

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

The paper establishes that any family of semialgebraic graphs in fixed dimension d admits an adjacency labeling scheme where each vertex gets a label of O(n^{1-2/(d+1) + ε}) bits. From any two labels one can decide if the corresponding vertices are adjacent, using only the information in those labels. This holds because the adjacency predicate is semialgebraic of constant complexity, allowing polynomial partitioning to decompose the space and assign labels based on the cells. The bound improves on prior results for such graphs and yields particularly good bounds for unit disk graphs and segment intersection graphs, both achieving O(n^{1/3 + ε}) bit labels. Additional results show O(log n) labels suffice for semilinear graphs and O(log^3 n) for polygon visibility graphs.

Core claim

By applying polynomial partitioning methods to the semialgebraic adjacency predicate, the authors construct labeling schemes in which each of the n vertices receives a label of O(n^{1-2/(d+1) + ε}) bits such that adjacency is determined solely from the two labels.

What carries the argument

Polynomial partitioning applied to the constant-complexity semialgebraic predicate defining adjacency.

If this is right

  • Unit disk graphs admit adjacency labels of O(n^{1/3 + ε}) bits.
  • Segment intersection graphs admit the same O(n^{1/3 + ε}) bit labels.
  • Semilinear graphs, a subclass using only linear polynomials, admit O(log n) bit labels.
  • Polygon visibility graphs admit O(log^3 n) bit labels.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The approach may extend to other geometric graph families whose adjacency can be captured by low-complexity algebraic conditions.
  • Such compact labels could enable more efficient distributed or streaming algorithms for these graph classes.
  • Coordinate representations sometimes require exponentially many bits, so the labeling provides a more compact implicit representation.

Load-bearing premise

The adjacency between vertices must be definable by a fixed semialgebraic predicate of constant complexity in constant dimension.

What would settle it

An explicit family of unit disk graphs on n vertices whose minimum adjacency label size exceeds n^{1/3 + ε} for small ε would falsify the bound.

Figures

Figures reproduced from arXiv: 2602.10922 by Jean Cardinal, Micha Sharir.

Figure 1
Figure 1. Figure 1: Example of an adjacency labeling of a graph (left). Here two vertices u and v are adjacent, hence A(ℓ(u), ℓ(v)) is true, if and only if the Hamming distance between the two labels ℓ(u) and ℓ(v) is exactly equal to one. The graph is therefore an induced subgraph of the cube (shown in red, right). any additional information about the graph. We focus on graphs defined by semialgebraic predi￾cates, which are c… view at source ↗
Figure 2
Figure 2. Figure 2: Example of an adjacency labeling of a graph with 16 edges (right) obtained from a biclique decompo￾sition of size 14 (left). The label ℓ(v) of a vertex v consists of the list of bicliques v is contained in, from the set {R, G, B}, together with an additional bit indicating on which side of the biclique the vertex v lies. Corollary 1. Unit disk graphs have an O(n 1/3+ε )-bit adjacency labeling scheme, for a… view at source ↗
Figure 3
Figure 3. Figure 3: The Perles configuration of 9 points and 9 lines, every realization of which requires at least one irrational coordinate. This provides an example of a semialgebraic family, the bipartite point-line incidence graphs, for which the natural implicit representation by real numbers cannot be turned into an adjacency labeling scheme with labels using a bounded number of bits. distance-hereditary graphs (that pr… view at source ↗
Figure 4
Figure 4. Figure 4: A schematic description of the partition tree used in the proof of Theorem 1. The top tree corresponds to the first phase, in which we repeatedly apply Lemma 4, and at the end of which we are left with leaves each containing at most N = n d/(d+1) elements of P. A dual partition tree is constructed from each leaf v by repeatedly applying Lemma 3. The blue and red subtrees depict the nodes in which, respecti… view at source ↗
Figure 5
Figure 5. Figure 5: The visibility graph of a simple polygon. 3.2 Decomposition We reduce the case of arbitrary semilinear graphs to that of bipartite comparability graphs, as is done in Tomon [82], and Cardinal and Yuditsky [28]. Proof of Theorem 2. As shown in [82], we can assume, without loss of generality, that the semilin￾ear family is defined by a predicate in the following disjunctive normal form: (u, v) ∈ E ⇔ _ i∈[k] … view at source ↗
Figure 6
Figure 6. Figure 6: A hereditary segment tree for a collection of line segments in the plane. The thicker red segment on the right is stored in the filled nodes of the tree, as a long segment in the two leaves, and as a short segment in the other nodes. 19 [PITH_FULL_IMAGE:figures/full_fig_p019_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: A slab containing a number of short blue (dashed) segments, and long red (solid) segments. Their intersection graph only depends on the relative vertical order of the endpoints, with respect to the vertically sorted sequence of the long segments, as shown in the alternative intersection model on the right. The resulting graph is therefore a two-dimensional bipartite comparability graph, with suitable inter… view at source ↗
Figure 8
Figure 8. Figure 8: Example of a visibility graph of points on an x-monotone curve. Such visibility graphs are capped graphs, since for any ordered 4-tuple of vertices vi , vj , vk and vℓ, if both pairs of vertices vivk and vjvℓ are adjacent, then so is vivℓ, as illustrated in the bottom left of the figure. segments exchanged. Our key observation is that these intersection graphs are two-dimensional bi￾partite comparability g… view at source ↗
read the original abstract

Semialgebraic graphs are graphs whose vertices are points in $\mathbb{R}^d$, and adjacency between two vertices is determined by the truth value of a semialgebraic predicate of constant complexity. We show how to harness polynomial partitioning methods to construct compact adjacency labeling schemes for families of semialgebraic graphs. That is, we show that for any family of semialgebraic graphs, given a graph on $n$ vertices in this family, we can assign a label consisting of $O(n^{1-2/(d+1) + \varepsilon})$ bits to each vertex (where $\varepsilon > 0$ can be made arbitrarily small and the constant of proportionality depends on $\varepsilon$ and on the complexity of the adjacency-defining predicate), such that adjacency between two vertices can be determined solely from their two labels, without any additional information. We obtain for instance that unit disk graphs and segment intersection graphs have such labelings with labels of $O(n^{1/3 + \varepsilon})$ bits. This is in contrast to their natural implicit representation consisting of the coordinates of the disk centers or segment endpoints, which sometimes require exponentially many bits. It also improves on the best known bound of $O(n^{1-1/d}\log n)$ for $d$-dimensional semialgebraic families due to Alon (Discrete Comput. Geom., 2024), a bound that holds more generally for graphs with shattering functions bounded by a degree-$d$ polynomial. We also give new bounds on the size of adjacency labels for other families of graphs. In particular, we consider semilinear graphs, which are semialgebraic graphs in which the predicate only involves linear polynomials. We show that semilinear graphs have adjacency labels of size $O(\log n)$. We also prove that polygon visibility graphs, which are not semialgebraic in the above sense, have adjacency labels of size $O(\log^3 n)$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript claims that polynomial partitioning techniques can be used to construct adjacency labeling schemes for semialgebraic graphs with vertices in R^d. Specifically, for any such family, a graph on n vertices admits labels of size O(n^{1-2/(d+1) + ε}) bits from which adjacency can be recovered, improving upon the O(n^{1-1/d} log n) bound of Alon. The paper also establishes O(log n) label size for semilinear graphs and O(log^3 n) for polygon visibility graphs.

Significance. This work strengthens the connection between the polynomial method and implicit graph representations. The improved exponent is significant for geometric graph classes like unit disk graphs, where previous implicit representations could require exponentially many bits. The O(log n) bound for semilinear graphs is a strong result that may have further applications. The construction is explicit and recursive, providing a clear algorithmic way to compute the labels.

major comments (2)
  1. [Main construction and recurrence analysis] The recurrence for label size (arising from recursive partitioning with degree r = n^δ) is central to the main theorem; the manuscript should include an explicit solution showing how the per-level cost of O(log r) bits plus the recursive term sums to the claimed O(n^{1-2/(d+1)+ε}) bound, including the precise dependence on the predicate complexity.
  2. [Semilinear graphs section] For the semilinear graphs result, the reduction to a constant number of linear partitions must specify the exact number of partitions required and confirm that the resulting recursion depth yields O(log n) total bits without hidden logarithmic factors from cell indexing.
minor comments (2)
  1. [Abstract and Theorem 1] The abstract states that the constant of proportionality depends on ε and predicate complexity; this dependence should be stated more explicitly in the theorem statement itself.
  2. [References] The citation to Alon (Discrete Comput. Geom., 2024) requires the full title and page range for completeness.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive assessment and constructive comments. We address each major comment below and will revise the manuscript to incorporate the clarifications.

read point-by-point responses

  1. Referee: The recurrence for label size (arising from recursive partitioning with degree r = n^δ) is central to the main theorem; the manuscript should include an explicit solution showing how the per-level cost of O(log r) bits plus the recursive term sums to the claimed O(n^{1-2/(d+1)+ε}) bound, including the precise dependence on the predicate complexity.

    Authors: We agree that an explicit closed-form solution to the recurrence will strengthen the presentation. In the revision we will add a dedicated paragraph (or short appendix) solving the recurrence L(n) ≤ c·log r + L(n/r^{1/d}) + O(1) for r = n^δ. By choosing δ = Θ(ε) sufficiently small relative to the fixed predicate complexity, the sum over O(log_{r} n) levels yields the stated O(n^{1-2/(d+1)+ε}) bound, with the leading constant depending only on ε and the predicate complexity (via the partitioning theorem constants). revision: yes

  2. Referee: For the semilinear graphs result, the reduction to a constant number of linear partitions must specify the exact number of partitions required and confirm that the resulting recursion depth yields O(log n) total bits without hidden logarithmic factors from cell indexing.

    Authors: We will revise the semilinear section to state explicitly that the predicate, being a Boolean combination of k linear inequalities (k constant), reduces to at most 2k linear partitions. With this fixed branching factor the recursion depth remains Θ(log n). Each level encodes the cell index in O(1) bits (using a canonical ordering of the constant number of cells), so the total label size is exactly O(log n) with no additional logarithmic factors. revision: yes

Circularity Check

0 steps flagged

No significant circularity in the derivation chain

full rationale

The paper's central construction is a recursive adjacency-labeling scheme that applies external polynomial-partitioning theorems directly to the input point set in R^d. At each recursion level a low-degree polynomial partitions the vertices; each label encodes a constant-size description of cell membership (sign sequence or index) plus the recursive label on the induced subgraph. The bit-length recurrence is solved by selecting partitioning degree r = n^δ at each step, yielding the O(n^{1-2/(d+1)+ε}) bound without any fitted parameters or self-referential definitions. The semilinear case reduces to a constant number of linear partitions, and the polygon-visibility result is proved separately. All load-bearing steps invoke independently established partitioning results rather than self-citations or quantities defined in terms of the target bound itself, rendering the derivation self-contained.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 0 invented entities

Relies on standard polynomial partitioning theorems from prior literature and the definition of constant-complexity semialgebraic predicates; no new free parameters or invented entities are introduced in the abstract.

free parameters (1)
  • ε
    Arbitrarily small positive constant whose dependence on predicate complexity is left implicit.
axioms (1)
  • domain assumption Polynomial partitioning applies to semialgebraic sets of constant complexity
    Invoked to obtain the labeling scheme; assumed from earlier work on partitioning.

pith-pipeline@v0.9.0 · 5660 in / 1117 out tokens · 34304 ms · 2026-05-16T05:49:53.198282+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

86 extracted references · 86 canonical work pages

  1. [1]

    Near-optimal induced universal graphs for bounded degree graphs

    Mikkel Abrahamsen, Stephen Alstrup, Jacob Holm, Mathias Bæk Tejs Knudsen, and Morten Stöckel. Near-optimal induced universal graphs for bounded degree graphs. In44th Interna- tional Colloquium on Automata, Languages, and Programming, volume 80, pages Art. No. 128, 14, 2017.doi:10.4230/LIPICS.ICALP.2017.128

    work page doi:10.4230/lipics.icalp.2017.128 2017

  2. [2]

    Near-optimal induced universal graphs for cycles and paths.Discrete Appl

    Mikkel Abrahamsen, Stephen Alstrup, Jacob Holm, Mathias Bæk Tejs Knudsen, and Morten Stöckel. Near-optimal induced universal graphs for cycles and paths.Discrete Appl. Math., 282:1–13, 2020.doi:10.1016/j.dam.2019.10.030

    work page doi:10.1016/j.dam.2019.10.030 2020

  3. [3]

    Labeling schemes for bounded degree graphs

    David Adjiashvili and Noy Rotbart. Labeling schemes for bounded degree graphs. In Automata, languages, and programming. Part II, volume 8573 ofLecture Notes in Com- put. Sci., pages 375–386. Springer, Heidelberg, 2014. URL:https://doi.org/10.1007/ 978-3-662-43951-7_32,doi:10.1007/978-3-662-43951-7\_32

    work page doi:10.1007/978-3-662-43951-7 2014

  4. [4]

    Pankaj K. Agarwal. Simplex range searching and its variants: a review. InA Journey Through Discrete Mathematics. A tribute to Jir ˇi Matoušek, pages 1–30. Springer, Cham, 2017.doi: 10.1007/978-3-319-44479-6_1

    work page doi:10.1007/978-3-319-44479-6_1 2017

  5. [5]

    Agarwal, Noga Alon, Boris Aronov, and Subhash Suri

    Pankaj K. Agarwal, Noga Alon, Boris Aronov, and Subhash Suri. Can visibility graphs be repre- sented compactly?Discrete Comput. Geom., 12(3):347–365, 1994.doi:10.1007/BF02574385. 22

    work page doi:10.1007/bf02574385 1994

  6. [6]

    Agarwal, Boris Aronov, Esther Ezra, Matthew J

    Pankaj K. Agarwal, Boris Aronov, Esther Ezra, Matthew J. Katz, and Micha Sharir. Intersec- tion queries for flat semi-algebraic objects in three dimensions and related problems.ACM Transactions on Algorithms, 21(3):25:1–25:59, 2025.doi:10.1145/3721290

    work page doi:10.1145/3721290 2025

  7. [7]

    Agarwal, Boris Aronov, Esther Ezra, and Joshua Zahl

    Pankaj K. Agarwal, Boris Aronov, Esther Ezra, and Joshua Zahl. Efficient algorithm for gener- alized polynomial partitioning and its applications.SIAM J. Comput., 50(2):760–787, 2021. doi:10.1137/19M1268550

    work page doi:10.1137/19m1268550 2021

  8. [8]

    Agarwal, Esther Ezra, and Micha Sharir

    Pankaj K. Agarwal, Esther Ezra, and Micha Sharir. Semi-algebraic off-line range searching and biclique partitions in the plane. In40th International Symposium on Computational Geometry, pages 4:1–4:15, 2024.doi:10.4230/LIPICS.SOCG.2024.4

    work page doi:10.4230/lipics.socg.2024.4 2024

  9. [9]

    Agarwal, Ji ˇrí Matoušek, and Micha Sharir

    Pankaj K. Agarwal, Ji ˇrí Matoušek, and Micha Sharir. On range searching with semialgebraic sets. II.SIAM J. Comput., 42(6):2039–2062, 2013.doi:10.1137/120890855

    work page doi:10.1137/120890855 2039

  10. [10]

    Agarwal and Kasturi R

    Pankaj K. Agarwal and Kasturi R. Varadarajan. Efficient algorithms for approximating polyg- onal chains.Discrete Comput. Geom., 23(2):273–291, 2000.doi:10.1007/PL00009500

    work page doi:10.1007/pl00009500 2000

  11. [11]

    Asymptotically optimal induced universal graphs.Geom

    Noga Alon. Asymptotically optimal induced universal graphs.Geom. Funct. Anal., 27(1):1–32, 2017.doi:10.1007/s00039-017-0396-9

    work page doi:10.1007/s00039-017-0396-9 2017

  12. [12]

    Implicit representation of sparse hereditary families.Discrete Comput

    Noga Alon. Implicit representation of sparse hereditary families.Discrete Comput. Geom., 72(2):476–482, 2024.doi:10.1007/s00454-023-00521-0

    work page doi:10.1007/s00454-023-00521-0 2024

  13. [13]

    Sign rank and the Vapnik-Chervonenkis di- mension.Mat

    Noga Alon, Shay Moran, and Amir Yehudayoff. Sign rank and the Vapnik-Chervonenkis di- mension.Mat. Sb., 208(12):4–41, 2017.doi:10.4213/sm8780

    work page doi:10.4213/sm8780 2017

  14. [14]

    Crossing patterns of semi-algebraic sets.J

    Noga Alon, János Pach, Rom Pinchasi, Radoš Radoiˇci´c, 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

    work page doi:10.1016/j.jcta 2005

  15. [15]

    Optimal induced universal graphs and adjacency labeling for trees.J

    Stephen Alstrup, Søren Dahlgaard, and Mathias Bæk Tejs Knudsen. Optimal induced universal graphs and adjacency labeling for trees.J. ACM, 64(4):Art. 27, 22, 2017.doi:10.1145/ 3088513

    work page 2017

  16. [16]

    Adjacency labeling schemes and induced-universal graphs.SIAM J

    Stephen Alstrup, Haim Kaplan, Mikkel Thorup, and Uri Zwick. Adjacency labeling schemes and induced-universal graphs.SIAM J. Discrete Math., 33(1):116–137, 2019.doi:10.1137/ 16M1105967

    work page 2019

  17. [17]

    Terrain visibility graphs: persistence is not enough

    Safwa Ameer, Matt Gibson-Lopez, Erik Krohn, Sean Soderman, and Qing Wang. Terrain visibility graphs: persistence is not enough. In36th International Symposium on Computa- tional Geometry, volume 164 ofLIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 6, 13. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2020.doi:10.4230/LIPICS.SOCG.2020.6

    work page doi:10.4230/lipics.socg.2020.6 2020

  18. [18]

    Subquadratic algorithms for some 3SUM-hard geometric problems in the algebraic decision- tree model.Comput

    Boris Aronov, Mark de Berg, Jean Cardinal, Esther Ezra, John Iacono, and Micha Sharir. Subquadratic algorithms for some 3SUM-hard geometric problems in the algebraic decision- tree model.Comput. Geom., 109:Paper No. 101945, 21, 2023.doi:10.1016/j.comgeo.2022. 101945. 23

    work page doi:10.1016/j.comgeo.2022 2023

  19. [19]

    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.doi:10.1016/j.comgeo.2021.101832

    work page doi:10.1016/j.comgeo.2021.101832 2022

  20. [20]

    ¯Onuki, R

    Aistis Atminas, Andrew Collins, Vadim Lozin, and Victor Zamaraev. Implicit representations and factorial properties of graphs.Discrete Math., 338(2):164–179, 2015.doi:10.1016/j. disc.2014.09.008

    work page doi:10.1016/j 2015

  21. [21]

    An adjacency labeling scheme based on a decomposition of trees into cater- pillars

    Avah Banerjee. An adjacency labeling scheme based on a decomposition of trees into cater- pillars. InCombinatorial algorithms, volume 13270 ofLecture Notes in Comput. Sci., pages 114–127. Springer, Cham, 2022.doi:10.1007/978-3-031-06678-8\_9

    work page doi:10.1007/978-3-031-06678-8 2022

  22. [22]

    Zarankiewicz’s problem for semilinear hypergraphs.Forum Math

    Abdul Basit, Artem Chernikov, Sergei Starchenko, Terence Tao, and Chieu-Minh Tran. Zarankiewicz’s problem for semilinear hypergraphs.Forum Math. Sigma, 9:Paper No. e59, 23, 2021.doi:10.1017/fms.2021.52

    work page doi:10.1017/fms.2021.52 2021

  23. [23]

    On the number of cells defined by a family of polynomials on a variety .Mathematika, 43(1):120–126, 1996.doi:10.1112/ S0025579300011621

    Saugata Basu, Richard Pollack, and Marie-Françoise Roy . On the number of cells defined by a family of polynomials on a variety .Mathematika, 43(1):120–126, 1996.doi:10.1112/ S0025579300011621

    work page 1996

  24. [24]

    Spinrad.Graph classes: a survey

    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

    work page doi:10.1137/1.9780898719796 1999

  25. [25]

    On counting point-hyperplane incidences.Computational Geometry, 25(1-2):13–20, 2003.doi:10.1016/S0925-7721(02)00127-X

    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

    work page doi:10.1016/s0925-7721(02)00127-x 2003

  26. [26]

    Geometric match- ing and bottleneck problems

    Sergio Cabello, Siu-Wing Cheng, Otfried Cheong, and Christian Knauer. Geometric match- ing and bottleneck problems. In40th International Symposium on Computational Geometry, volume 293, pages 31:1–31:15, 2024.doi:10.4230/LIPICS.SOCG.2024.31

    work page doi:10.4230/lipics.socg.2024.31 2024

  27. [27]

    Improved algebraic degeneracy testing.Discrete Comput

    Jean Cardinal and Micha Sharir. Improved algebraic degeneracy testing.Discrete Comput. Geom., 74(1):177–195, 2025.doi:10.1007/s00454-024-00673-7

    work page doi:10.1007/s00454-024-00673-7 2025

  28. [28]

    Compact Representation of Semilinear and Terrain-Like Graphs

    Jean Cardinal and Yelena Yuditsky . Compact Representation of Semilinear and Terrain-Like Graphs. In33rd Annual European Symposium on Algorithms (ESA 2025), volume 351 of Leibniz International Proceedings in Informatics (LIPIcs), pages 67:1–67:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025.doi:10.4230/LIPIcs.ESA.2025.67

    work page doi:10.4230/lipics.esa.2025.67 2025

  29. [29]

    Halldórsson, Magnús M

    Daniele Catanzaro, Steven Chaplick, Stefan Felsner, Bjarni V. Halldórsson, Magnús M. Halldórsson, Thomas Hixon, and Juraj Stacho. Max point-tolerance graphs.Discrete Appl. Math., 216:84–97, 2017.doi:10.1016/j.dam.2015.08.019

    work page doi:10.1016/j.dam.2015.08.019 2017

  30. [30]

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

    work page doi:10.1137/s009753970343912x 2006

  31. [31]

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

    work page doi:10.1007/s00454-012-9410-z 2012

  32. [32]

    Logical labeling schemes.Discrete Math., 346(10):Paper No

    Maurice Chandoo. Logical labeling schemes.Discrete Math., 346(10):Paper No. 113565, 21, 2023.doi:10.1016/j.disc.2023.113565. 24

    work page doi:10.1016/j.disc.2023.113565 2023

  33. [33]

    Grid intersection graphs and order dimension.Order, 35(2):363–391, 2018.doi:10.1007/s11083-017-9437-0

    Steven Chaplick, Stefan Felsner, Udo Hoffmann, and Veit Wiechert. Grid intersection graphs and order dimension.Order, 35(2):363–391, 2018.doi:10.1007/s11083-017-9437-0

    work page doi:10.1007/s11083-017-9437-0 2018

  34. [34]

    A theorem on polygon cutting with applications

    Bernard Chazelle. A theorem on polygon cutting with applications. In23rd annual symposium on foundations of computer science (Chicago, Ill., 1982), pages 339–349. IEEE, New York, 1982. doi:10.1109/SFCS.1982.58

    work page doi:10.1109/sfcs.1982.58 1982

  35. [35]

    Cutting hyperplanes for divide-and-conquer.Discrete Comput

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

    work page doi:10.1007/bf02189314 1993

  36. [36]

    Guibas, and Micha Sharir

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

    work page doi:10.1007/bf01182771 1994

  37. [37]

    Bernard Chazelle and Leonidas J. Guibas. Visibility and intersection problems in plane geom- etry .Discrete Comput. Geom., 4(6):551–581, 1989.doi:10.1007/BF02187747

    work page doi:10.1007/bf02187747 1989

  38. [38]

    Quasi-optimal range searching in spaces of finite VC- dimension.Discrete Comput

    Bernard Chazelle and Emo Welzl. Quasi-optimal range searching in spaces of finite VC- dimension.Discrete Comput. Geom., 4(5):467–489, 1989.doi:10.1007/BF02187743

    work page doi:10.1007/bf02187743 1989

  39. [39]

    Fan R. K. Chung, Paul Erd˝os, and Joel Spencer. On the decomposition of graphs into complete bipartite subgraphs. InStudies in pure mathematics: To the Memory of Paul Turán, pages 95–101. Birkhäuser, Basel, 1983.doi:10.1007/978-3-0348-5438-2_10

    work page doi:10.1007/978-3-0348-5438-2_10 1983

  40. [40]

    Ramsey-type results for semi-algebraic relations.Trans

    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

    work page 2014

  41. [41]

    Journées de l’Informatique Messine

    B. Courcelle and R. Vanicat. Query efficient implementation of graphs of bounded clique- width.Discrete Appl. Math., 131(1):129–150, 2003. The Second International Colloquium “ Journées de l’Informatique Messine” (Metz, 2000).doi:10.1016/S0166-218X(02)00421-3

    work page doi:10.1016/s0166-218x(02)00421-3 2003

  42. [42]

    Coloring polygon visibility graphs and their generalizations.J

    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

    work page doi:10.1016/j.jctb.2023.02.010 2023

  43. [43]

    Visibility graphs

    Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars. Visibility graphs. InComputational Geometry. Algorithms and Applications, Third Edition, chapter 15. Springer, 2008.doi:10.1007/978-3-540-77974-2

    work page doi:10.1007/978-3-540-77974-2 2008

  44. [44]

    Representation complexities of semialgebraic graphs.SIAM J

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

    work page doi:10.1137/18m1221606 2019

  45. [45]

    Adjacency labelling for planar graphs (and beyond).J

    Vida Dujmovi ´c, Louis Esperet, Cyril Gavoille, Gwenaël Joret, Piotr Micek, and Pat Morin. Adjacency labelling for planar graphs (and beyond).J. ACM, 68(6):Art. 42, 33, 2021.doi: 10.1145/3477542

    work page doi:10.1145/3477542 2021

  46. [46]

    Covering a graph by complete bipartite graphs.Discrete Math., 170(1-3):249–251, 1997.doi:10.1016/S0012-365X(96)00124-0

    Paul Erd ˝os and László Pyber. Covering a graph by complete bipartite graphs.Discrete Math., 170(1-3):249–251, 1997.doi:10.1016/S0012-365X(96)00124-0. 25

    work page doi:10.1016/s0012-365x(96)00124-0 1997

  47. [47]

    New lower bounds for Hopcroft’s problem.Discrete Comput

    Jeff Erickson. New lower bounds for Hopcroft’s problem.Discrete Comput. Geom., 16(4):389– 418, 1996.doi:10.1007/BF02712875

    work page doi:10.1007/bf02712875 1996

  48. [48]

    On characterizing terrain visibility graphs.J

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

    work page doi:10.20382/jocg.v6i1a5 2015

  49. [49]

    Clique partitions, graph compression and speeding-up algorithms.J

    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

    work page doi:10.1006/jcss.1995.1065 1995

  50. [50]

    Implicit representation conjecture for semi-algebraic graphs.Discrete Appl

    Matthew Fitch. Implicit representation conjecture for semi-algebraic graphs.Discrete Appl. Math., 259:53–62, 2019.doi:10.1016/j.dam.2018.11.030

    work page doi:10.1016/j.dam.2018.11.030 2019

  51. [51]

    Overlap properties of geometric expanders.J

    Jacob Fox, Mikhail Gromov, Vincent Lafforgue, Assaf Naor, and János Pach. Overlap properties of geometric expanders.J. Reine Angew. Math., 671:49–83, 2012.doi:10.1515/crelle. 2011.157

    work page doi:10.1515/crelle 2012

  52. [52]

    A semi-algebraic version of Zarankiewicz’s problem.J

    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

    work page 2017

  53. [53]

    A polynomial regularity lemma for semialge- braic hypergraphs and its applications in geometry and property testing.SIAM J

    Jacob Fox, János Pach, and Andrew Suk. A polynomial regularity lemma for semialge- braic hypergraphs and its applications in geometry and property testing.SIAM J. Comput., 45(6):2199–2223, 2016.doi:10.1137/15M1007355

    work page doi:10.1137/15m1007355 2016

  54. [54]

    Ramsey-Turán numbers for semi-algebraic graphs

    Jacob Fox, János Pach, and Andrew Suk. Ramsey-Turán numbers for semi-algebraic graphs. Electron. J. Combin., 25(4):Paper No. 4.61, 5, 2018.doi:10.37236/7988

    work page doi:10.37236/7988 2018

  55. [55]

    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.doi:10.1016/j.ejc.2023.103780

    work page doi:10.1016/j.ejc.2023.103780 2024

  56. [56]

    Ghosh.Visibility Algorithms in the Plane

    Subir K. Ghosh.Visibility Algorithms in the Plane. Cambridge University Press, 2007.doi: 10.1017/CBO9780511543340

    work page doi:10.1017/cbo9780511543340 2007

  57. [57]

    Goodman, Richard Pollack, and Bernd Sturmfels

    Jacob E. Goodman, Richard Pollack, and Bernd Sturmfels. Coordinate representation of order types requires exponential storage. InProceedings of the 21st Annual ACM Symposium on Theory of Computing, pages 405–410, 1989.doi:10.1145/73007.73046

    work page doi:10.1145/73007.73046 1989

  58. [58]

    Polynomial partitioning for a set of varieties.Math

    Larry Guth. Polynomial partitioning for a set of varieties.Math. Proc. Cambridge Philos. Soc., 159(3):459–469, 2015.doi:10.1017/S0305004115000468

    work page doi:10.1017/s0305004115000468 2015

  59. [59]

    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.doi:10.4007/annals.2015.181.1.2

    work page doi:10.4007/annals.2015.181.1.2 2015

  60. [60]

    The implicit graph conjecture is false

    Hamed Hatami and Pooya Hatami. The implicit graph conjecture is false. In63rd Annual IEEE Symposium on Foundations of Computer Science, pages 1134–1137. IEEE, 2022.doi: 10.1109/FOCS54457.2022.00109

    work page doi:10.1109/focs54457.2022.00109 2022

  61. [61]

    Generalizations of the Szemerédi-Trotter theorem.Discrete Comput

    Saarik Kalia, Micha Sharir, Noam Solomon, and Ben Yang. Generalizations of the Szemerédi-Trotter theorem.Discrete Comput. Geom., 55(3):571–593, 2016.doi:10.1007/ s00454-016-9759-5. 26

    work page 2016

  62. [62]

    Implicit representation of graphs.SIAM J

    Sampath Kannan, Moni Naor, and Steven Rudich. Implicit representation of graphs.SIAM J. Discrete Math., 5(4):596–603, 1992.doi:10.1137/0405049

    work page doi:10.1137/0405049 1992

  63. [63]

    Unit distances in three dimensions.Combin

    Haim Kaplan, Ji ˇrí Matoušek, Zuzana Safernová, and Micha Sharir. Unit distances in three dimensions.Combin. Probab. Comput., 21(4):597–610, 2012.doi:10.1017/ S0963548312000144

    work page 2012

  64. [64]

    Simple proofs of classical theorems in dis- crete geometry via the Guth-Katz polynomial partitioning technique.Discrete Comput

    Haim Kaplan, Ji ˇrí Matoušek, and Micha Sharir. Simple proofs of classical theorems in dis- crete geometry via the Guth-Katz polynomial partitioning technique.Discrete Comput. Geom., 48(3):499–517, 2012.doi:10.1007/s00454-012-9443-3

    work page doi:10.1007/s00454-012-9443-3 2012

  65. [65]

    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.doi:10.1137/S0097539794268649

    work page doi:10.1137/s0097539794268649 1997

  66. [66]

    Intersection graphs of segments.J

    Jan Kratochvíl and Ji ˇrí Matoušek. Intersection graphs of segments.J. Combin. Theory Ser. B, 62(2):289–315, 1994.doi:10.1006/jctb.1994.1071

    work page doi:10.1006/jctb.1994.1071 1994

  67. [67]

    Efficient partition trees.Discrete Comput

    Ji ˇrí Matoušek. Efficient partition trees.Discrete Comput. Geom., 8(3):315–334, 1992.doi: 10.1007/BF02293051

    work page doi:10.1007/bf02293051 1992

  68. [68]

    Range searching with efficient hierarchical cuttings.Discrete Comput

    Ji ˇrí Matoušek. Range searching with efficient hierarchical cuttings.Discrete Comput. Geom., 10(2):157–182, 1993.doi:10.1007/BF02573972

    work page doi:10.1007/bf02573972 1993

  69. [69]

    Multilevel polynomial partitions and simplified range searching.Discrete Comput

    Ji ˇrí 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

    work page doi:10.1007/s00454-015-9701-2 2015

  70. [70]

    Integer realizations of disk and segment graphs.J

    Colin McDiarmid and Tobias Müller. Integer realizations of disk and segment graphs.J. Combin. Theory Ser. B, 103(1):114–143, 2013.doi:10.1016/j.jctb.2012.09.004

    work page doi:10.1016/j.jctb.2012.09.004 2013

  71. [71]

    On the Betti numbers of real varieties.Proc

    John Milnor. On the Betti numbers of real varieties.Proc. Amer. Math. Soc., 15:275–280, 1964.doi:10.2307/2034050

    work page doi:10.2307/2034050 1964

  72. [72]

    Nicolai E. Mnëv. The universality theorems on the classification problem of configura- tion varieties and convex polytopes varieties. InTopology and Geometry—Rohlin Semi- nar, volume 1346 ofLecture Notes in Math., pages 527–543. Springer, Berlin, 1988.doi: 10.1007/BFb0082792

    work page doi:10.1007/bfb0082792 1988

  73. [73]

    Muller.Local structure in graph classes

    John H. Muller.Local structure in graph classes. PhD thesis, Georgia Institute of Technology , USA, 1988

    work page 1988

  74. [74]

    Visibility

    Joseph O’Rourke. Visibility . InHandbook of Discrete and Computational Geometry, 3rd Edition, chapter 33. Chapman and Hall/CRC, 2017.doi:10.1201/9781315119601

    work page doi:10.1201/9781315119601 2017

  75. [75]

    An efficient regularity lemma for semi-algebraic hypergraphs

    Natan Rubin. An efficient regularity lemma for semi-algebraic hypergraphs. InProceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3611–3636. SIAM, Philadelphia, PA, 2025.doi:10.1137/1.9781611978322.120

    work page doi:10.1137/1.9781611978322.120 2025

  76. [76]

    On the speed of algebraically defined graph classes.Adv

    Lisa Sauermann. On the speed of algebraically defined graph classes.Adv. Math., 380:Paper No. 107593, 55, 2021.doi:10.1016/j.aim.2021.107593. 27

    work page doi:10.1016/j.aim.2021.107593 2021

  77. [77]

    Incidences between points and lines inR4.Discrete Comput

    Micha Sharir and Noam Solomon. Incidences between points and lines inR4.Discrete Comput. Geom., 57(3):702–756, 2017.doi:10.1007/s00454-016-9822-2

    work page doi:10.1007/s00454-016-9822-2 2017

  78. [78]

    Peter W. Shor. Stretchability of pseudolines is NP-hard. InApplied Geometry and Discrete Mathematics, volume 4 ofDIMACS Ser. Discrete Math. Theoret. Comput. Sci., pages 531–554. Amer. Math. Soc., Providence, RI, 1991.doi:10.1090/dimacs/004/41

    work page doi:10.1090/dimacs/004/41 1991

  79. [79]

    An incidence theorem in higher dimensions.Discrete Com- put

    József Solymosi and Terence Tao. An incidence theorem in higher dimensions.Discrete Com- put. Geom., 48(2):255–280, 2012.doi:10.1007/s00454-012-9420-x

    work page doi:10.1007/s00454-012-9420-x 2012

  80. [80]

    Spinrad.Efficient graph representations, volume 19 ofFields Institute Monographs

    Jeremy P. Spinrad.Efficient graph representations, volume 19 ofFields Institute Monographs. American Mathematical Society , Providence, RI, 2003.doi:10.1090/fim/019

    work page doi:10.1090/fim/019 2003

Showing first 80 references.