Pith. sign in

REVIEW 3 major objections 3 minor 55 references

Layered tree-independence number and clique-based separators

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

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

Pith's one-line read This paper proves bounded layered tree-independence number for g-map graphs, hyperbolic uniform disk graphs, and spherical uniform disk graphs, and combines this with bounded clique cover degeneracy to obtain clique-based separators of…

desk verdict Strong new bounds on layered tree-independence number for map graphs and non-Euclidean disk graphs; a few fixable proof slips, but the core is sound. read the letter →

arxiv 2506.12424 v1 pith:ZO6TK3K3 submitted 2025-06-14 math.CO cs.CGcs.DM

Clément Dallard , Martin Milanič , Andrea Munaro , Shizhou Yang This is my paper · ORCID
classification math.COcs.CGcs.DM MSC 05C1005C6205C7505C85
keywords layeredtree-independencenumberclique-basedseparatorsmapgraphshyperbolicuniformdisksphericalcliquecoverdegeneracygeometricintersection
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

This paper studies a structural question: if a graph class has bounded layered tree-independence number—a measure of how well a graph can be decomposed into a tree of bags while each bag stays small in each vertex layer—does it always have balanced separators built from disjoint cliques with sublinear total weight? The authors establish bounded layered tree-independence for g-map graphs, hyperbolic uniform disk graphs of radius r, and spherical uniform disk graphs of radius r, with explicit bounds. They then show that for these classes the structural bound combines with bounded clique cover degeneracy to produce clique-based separators of sublinear size, giving positive evidence for the open question. The same bounds lead to subexponential or quasi-polynomial algorithms for weighted problems such as Max Weight Independent Set and Min Weight Feedback Vertex Set on these geometric graph classes.

What carries the argument

The load-bearing device is the r-neighborhood cliquification: given a graph G and a set P of vertices, add all missing edges among vertices within distance r of each p in P. For a graph with layered treewidth k, the cliquification has layered tree-independence number at most 4rk, and the proof builds the new layering by merging 2r consecutive layers and enlarging each bag along shortest paths to P. g-map graphs arise as such cliquifications of bounded-genus bipartite witnesses, and odd and even powers arise from cliquifications of pendant-edge gadgets. For hyperbolic and spherical uniform disk graphs, the proof uses a polar-coordinate model: layers are radial annuli of width 2r, bags are angular rays, and the bound on independent vertices inside a bag-layer intersection comes from a packing argument—for hyperbolic disks, subdividing each annulus into Saccheri quadrilaterals whose diameter is at most 2r; for spherical disks, an area-ratio estimate showing at most 15 disjoint disks can sit in each half of a bag-layer intersection. Finally, bounded clique cover degeneracy supplies the linear θ-binding function f(x)=kx that converts a balanced bag of independence number O(√n) into a clique-based separator of sublinear weight.

What would settle it

Compute the actual hyperbolic diameter of the Saccheri quadrilateral with base $\tanh r$ and legs $r$; if for some $r$ this diameter exceeds $2r$, then two disjoint radius-$r$ disks can fit in one cell of the partition used in Theorem 3.12, and the $6\lceil r/\tanh r\rceil$ bound collapses.

Watch

Extended reading notes

Core claim

The paper's central discovery is that bounded layered tree-independence number, although not known to imply sublinear clique-based separators in general, does imply them once bounded clique cover degeneracy is added. Concretely, Corollary 3.6 gives a polynomial-time computable tree decomposition and layering of any g-map graph witnessing layered tree-independence number at most 6g+9; Theorem 3.12 gives 6⌈r/tanh r⌉ for hyperbolic uniform disk graphs of radius r; Theorem 3.15 gives the radius-independent bound 30 for spherical uniform disk graphs. Section 4 bounds clique cover degeneracy by 3 for 0-map graphs, by 6 for spherical uniform disk graphs, and by 4 for contact string graphs. Combining these, Corollary 5.3 yields clique-based separators of size O(√n) for 0-map graphs and unit disk graphs, O(√(r/tanh r)·√n) for hyperbolic uniform disk graphs, and O(√n) for spherical uniform disk graphs. The same machinery also shows that powers of bounded layered treewidth graphs have bounded layered tree-independence number, and that contact segment graphs have unbounded layered tree-independence number, so contact string graphs are not all 0-map graphs.

Load-bearing premise

The hyperbolic radius bound rests on a cited geometric lemma saying each Saccheri quadrilateral of base $\tanh r$ and legs $r$ has diameter at most $2r$; the whole packing argument for that theorem depends on this one estimate.

Editorial extensions

If this is right

  • Every n-vertex g-map graph, spherical uniform disk graph, and unit disk graph admits a clique-based separator of size O(√n) that can be computed in polynomial time from a suitable realization.
  • Hyperbolic uniform disk graphs of radius r admit clique-based separators of size O(√(r/tanh r)·√n), interpolating between the Euclidean-like regime of bounded r and the firmly hyperbolic regime of large r.
  • Max Weight Independent Set and Min Weight Feedback Vertex Set, and more generally Max Weight Distance-d Packing for even d, have 2^{O(√n log n)}-time algorithms on g-map graphs and spherical uniform disk graphs, and quasi-polynomial-time algorithms on hyperbolic uniform disk graphs when r is not too small.
  • Powers of bounded layered treewidth graphs have bounded layered tree-independence number, so the separator and algorithmic consequences apply to those powers as well.
  • Contact segment graphs have unbounded local tree-independence number, while contact string graphs still have clique cover degeneracy at most 4 and hence chromatic number at most 4 times the clique number.

Reading between the lines

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

  • Beyond the paper, the same recipe—bounded layered tree-independence number plus bounded clique cover degeneracy implies sublinear clique-based separators—could be tested on other geometric intersection classes where one bound is known but the other is not yet established.
  • The separation between contact segment graphs and 0-map graphs suggests a finer hierarchy: one-sided contact string graphs sit inside 0-map graphs, while general contact string graphs do not, so probing which intermediate contact classes inherit bounded layered tree-independence would be a natural next step.
  • If the Saccheri-quadrilateral diameter bound ever failed, the hyperbolic theorem as stated would need repair, but the spherical and map-graph results would remain intact, so the overall positive evidence for Question 1.2 would not be threatened.
  • Resolving Question 7.1 affirmatively would improve the hyperbolic layered tree-independence bound to a constant, which by the paper's Lemma 6.1 would also give bounded independence degeneracy for hyperbolic uniform disk graphs.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 3 minor

Summary. The paper studies layered tree-independence number, clique cover degeneracy, independence degeneracy, and clique-based separators for geometric intersection graphs. Its central structural contributions are: O(g) layered tree-independence number for g-map graphs (Corollary 3.6), O(r/tanh r) for hyperbolic uniform disk graphs of radius r (Theorem 3.12), O(1) for spherical uniform disk graphs (Theorem 3.15), and bounded layered tree-independence number for powers of bounded layered-treewidth graphs. Section 4 bounds clique cover degeneracy for 0-map graphs, spherical disk graphs, and contact string graphs; Section 5 combines these bounds to produce sublinear-weight clique-based separators; Section 6 proves that every fractionally tree-α-fragile class is polynomially (dgn,ω)-bounded and formulates Conjecture 1.4. Algorithmic corollaries for weighted Max Weight Independent Set, Min Weight Feedback Vertex Set, and related problems are derived from these bounds.

Significance. If the results stand, they give strong positive evidence for Question 1.2 on several important classes and extend subexponential-time weighted algorithms to geometric graphs where only unweighted algorithms were previously known. The r-neighborhood cliquification operation (Theorem 3.1) is a clean and reusable tool. The paper is careful about explicit constants and about separating structural from algorithmic statements; the main proofs are mostly self-contained, with only standard geometric facts imported from [8]. The two proof gaps I found are local and repairable, and I do not see a threat to the central claims.

major comments (3)
  1. [Theorem 3.12, proof of (11)] The proof as written contains an invalid geometric justification. The sentence 'if c ∉ R′, then the line through c perpendicular to ℓ... must intersect one of ℓ0 and ℓh, contradicting the fact that no two parallel lines intersect' is not a valid argument: a line perpendicular to ℓ at a point beyond s0 or before sh is simply another disjoint perpendicular, not a line crossing ℓ0 or ℓh. Moreover, the claimed strict inequality b(s) < 2jr can fail when the center c lies on the ray Si at distance exactly 2jr, since Rj is defined with a closed upper endpoint. The intended conclusion is recoverable: the correct bound is (2j−3)r ≤ b(s) ≤ 2jr, and since h tanh r ≥ 3r, the foot s lies between s0 and sh; together with d(c,ℓ) ≤ r this places c in R′. The proof should be repaired by replacing the strict inequality with a non-strict one and by deleting or correcting the parallel-lines sentence.
  2. [Theorem 3.15, proof of (13)–(14)] The areal argument bounding the number of pairwise non-intersecting disks by (1−cos 4r)/(1−cos r) is only valid when 4r ≤ π. If 4r > π, the 'disk of radius 4r' centered at z is the whole sphere, whose area is 4π, not 2π(1−cos 4r). This case is not handled in the manuscript. The bound 15 is still correct: for r ≥ π/4, the area of S2 gives at most 4π/(2π(1−cos r)) = 2/(1−cos r) < 16, so the final 15+15=30 estimate survives. The proof should be split into the cases 4r ≤ π and 4r > π, or an equivalent argument should be provided.
  3. [Theorem 3.15, proof of (13), existence of the point z] The proof chooses z = ((2j−1)r, zi) on the ray Si. This is legitimate only when (2j−1)r ≤ π, and the manuscript does not state why this holds. The missing justification is that if (2j−1)r > π, then every center c with b(c) > (2j−2)r satisfies π − b(c) < r, so the disk centered at c contains the antipode o∗ and therefore intersects the polar axis ℓ; such a vertex belongs to U, not U′. Thus for a vertex in Xti ∩ Vj ∩ U′, the quantity (2j−1)r is indeed at most π. This is a local omission, but it should be made explicit so that the construction of z is fully justified.
minor comments (3)
  1. [Corollary 3.6] The proof invokes Theorem 3.4, which is stated for connected graphs. A witness H of a g-map graph may be disconnected; the proof should either state that H can be assumed connected without loss of generality or explain how to combine the component-wise tree decompositions and layerings.
  2. [Theorems 3.12 and 3.15] The algorithmic statements depend on the input graph being given together with a geometric realization, as noted in the preceding remarks. This convention should be moved into the theorem statements themselves, since the claimed O(n log n) computation of θ− and θ+ values is only meaningful with that input.
  3. [Proposition 4.2] In the replacement step, the sentence claiming that a Euclidean disk C of the same radius as φ(A) can be drawn inside φ(B) and tangent to φ(A) at φ(s) is terse. A one-sentence justification of why such a disk exists would improve readability and remove any ambiguity about the containment.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main bounds are proved from geometry and graph structure; self-citations are background only.

full rationale

The central claims (Corollary 3.6, Theorem 3.12, Theorem 3.15) are derived constructively: a layering by radial distance, a ray-based path decomposition, and an independence bound in each bag-layer intersection. The hyperbolic bound depends on an external geometric lemma [8, Lemma 8] on Saccheri quadrilaterals, not on any result of the present authors. The spherical bound uses only area comparison and elementary trigonometry. The paper does cite prior work of its own authors ([31], [32]) for the definition of layered tree-independence number, for the conversion Lemma 2.2, and for the motivating Question 1.2; these are background or corollary tools, not inputs that reappear as conclusions. In particular, Lemma 2.2 is a parameter-free theorem with stated assumptions not including any of the geometric bounds, so citing it is legitimate independent support. There is a minor proof slip in (11) ('no two parallel lines intersect'), but the needed conclusion that the perpendicular through c falls inside the interval follows from the already established inequality (2j-3)r <= b(s) < 2jr; it is a recoverable editing error, not a circular reduction. Likewise, the area-ratio count in Theorem 3.15 needs a one-line case split for 4r > pi, but the stated bound still follows. No fitted parameter is relabeled as a prediction, and no uniqueness theorem is imported from the authors' prior work to force a choice. The derivation chain is therefore self-contained.

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

The central claim rests on standard graph theory (tree decompositions, Ramsey theory), on geometric facts about hyperbolic and spherical geometry (some cited from prior papers, notably the Saccheri quadrilateral diameter bound of [8]), and on an input-representation convention for geometric graphs. No data-fitting parameters or ad hoc entities are introduced.

assumptions (9)
  • domain assumption Each Saccheri quadrilateral with base length tanh r and legs of length r has diameter at most 2r.
    Cited from Blasius et al. [8, Lemma 8] in the proof of Theorem 3.12 to bound the number of non-intersecting disk centers per region.
  • domain assumption Line graphs of grids have unbounded tree-independence number.
    Used in Proposition 3.9 to show contact segment graphs have unbounded local tree-independence number; cited to [12, Theorem 3].
  • domain assumption Every planar graph has a vertex whose neighborhood is the union of 3 cliques.
    Used in Proposition 4.1 for 0-map graphs; cited to Ye and Borodin [55].
  • domain assumption The neighborhood of every smallest disk in a Euclidean disk graph is the union of 6 cliques.
    Used in Proposition 4.2 for spherical disk graphs; cited to Kammer and Tholey [38, Lemma 6].
  • standard math Every tree decomposition of a graph has a node t and vertex u with N[u] subset of X_t.
    Used in Lemma 6.1; cited to Dallard et al. [19, Lemma 2.6].
  • standard math Standard properties of hyperbolic geometry (polar coordinates, perpendiculars, equidistant curves, triangle inequality, Saccheri quadrilaterals).
    Used throughout Theorem 3.12; background from Ramsay and Richtmyer [52].
  • domain assumption Input convention: geometric graphs are given with a geometric realization (e.g., polar coordinates of disk centers); g-map graphs are given with a witness H (or an embedding).
    Needed for the polynomial-time constructions in Corollary 3.6, Theorems 3.12 and 3.15; the paper states this as 'without loss of generality' but it is in fact an input model assumption.
  • standard math Ramsey's theorem and the standard upper bound R(p,q) <= binom(p+q-2, p-1).
    Used in Proposition 5.4, Lemma 6.4, and Corollary 6.8.
  • standard math For every graph G, dgn(G) <= tw(G) and ad(G) <= 2 dgn(G).
    Used in Lemma 6.7; references [11] and [14, Corollary 1].

how reviews work

0 comments
Cite this review

Pith. "Pith review of Layered tree-independence number and clique-based separators." pith.science (2026). https://pith.science/paper/ZO6TK3K3

@misc{pith2026250612424,
  author       = {Pith},
  title        = {Pith review of: Layered tree-independence number and clique-based separators},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZO6TK3K3}},
  note         = {Machine review of arXiv:2506.12424}
}
abstract

Motivated by a question of Galby, Munaro, and Yang (SoCG 2023) asking whether every graph class of bounded layered tree-independence number admits clique-based separators of sublinear weight, we investigate relations between layered tree-independence number, weight of clique-based separators, clique cover degeneracy and independence degeneracy. In particular, we provide a number of results bounding these parameters on geometric intersection graphs. For example, we show that the layered tree-independence number is $\mathcal{O}(g)$ for $g$-map graphs, $\mathcal{O}(\frac{r}{\tanh r})$ for hyperbolic uniform disk graphs with radius $r$, and $\mathcal{O}(1)$ for spherical uniform disk graphs with radius $r$. Our structural results have algorithmic consequences. In particular, we obtain a number of subexponential or quasi-polynomial-time algorithms for weighted problems such as \textsc{Max Weight Independent Set} and \textsc{Min Weight Feedback Vertex Set} on several geometric intersection graphs. Finally, we conjecture that every fractionally tree-independence-number-fragile graph class has bounded independence degeneracy.

Figures

Figures reproduced from arXiv: 2506.12424 by the authors.

Figure 1
Figure 1. Relationships between the main graph class properties related to the paper, where an [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Examples of line segments in R 2 yielding contact segment graphs with radius 2 and unbounded tree-independence number. Examples on the right extend the ones on the left, in the sense that sufficiently large examples of the right type contain any fixed example of the left type (as indicated by the bold part of the figure on the right). Proposition 3.9. The class of contact segment graphs has unbounded local tree-inde… view at source ↗
Figure 3
Figure 3. A representation of a 0-map graph G which is not contact string. Each Ai and A′ i consists of n nations, where n is sufficiently large (see Proposition 3.10). The graph G has 18n+ 9 + 1 vertices, corresponding to the faces of the plane graph G0 drawn in blue, which are all nations. Proposition 3.10. There exist 0-map graphs which are not contact string graphs. Proof. We show that the 0-map graph in [PITH_FULL_IMAGE… view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Construction of a planar bipartite witness [PITH_FULL_IMAGE:figures/full_fig_p022_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

55 extracted references · 50 canonical work pages

  1. [8]

    Structure and Independence in Hyperbolic Uniform Disk Graphs

    Thomas Bläsius, Jean-Pierre von der Heydt, Sándor Kisfaludi-Bak, Marcus Wilhelm, and Geert van Wordragen. Structure and independence in hyperbolic uniform disk graphs.CoRR, abs/2407.09362, 2024. URL https://arxiv.org/abs/2407.09362

    work page Pith review arXiv 2024

  2. [1]

    Halldórsson

    Geir Agnarsson and Magnús M. Halldórsson. Coloring powers of planar graphs.SIAM Journal on Discrete Mathematics, 16(4):651–662, 2003

    work page 2003

  3. [2]

    Opportunity cost algorithms for combinatorial auctions

    Karhan Akcoglu, James Aspnes, Bhaskar DasGupta, and Ming-Yang Kao. Opportunity cost algorithms for combinatorial auctions. In Erricos John Kontoghiorghes, Berc Rustem, and Stavros Siokos, editors,Computational Methods in Decision-Making, Economics and Finance, pages 455–479. Springer US, 2002

    work page 2002

  4. [3]

    Faster Algorithms for Cycle Hitting Problems on Disk Graphs

    Shinwoo An, Kyungjin Cho, and Eunjin Oh. Faster algorithms for cycle hitting problems on disk graphs. CoRR, abs/2311.03665, 2023. URLhttps://arxiv.org/abs/2311.03665

    work page Pith review arXiv 2023

  5. [4]

    On forbidden induced subgraphs for unit disk graphs

    Aistis Atminas and Viktor Zamaraev. On forbidden induced subgraphs for unit disk graphs. Discrete & Computational Geometry, 60(1):57–97, 2018

    work page 2018

  6. [5]

    On approximation properties of the independent set problem for low degree graphs.Theory of Computing Systems, 32(2):115–132, 1999

    Piotr Berman and Toshihiro Fujito. On approximation properties of the independent set problem for low degree graphs.Theory of Computing Systems, 32(2):115–132, 1999

    work page 1999

  7. [6]

    Feedback Vertex Set for pseudo-disk graphs in subexponential FPT time

    Gaétan Berthe, Marin Bougeret, Daniel Gonçalves, and Jean-Florent Raymond. Feedback Vertex Set for pseudo-disk graphs in subexponential FPT time.CoRR, abs/2410.23878, 2024. URL https://arxiv.org/abs/2410.23878. 33

    work page Pith review arXiv 2024

  8. [7]

    Recognizing Unit Disk Graphs in Hyperbolic Geometry is $\exists\mathbb{R}$-Complete

    Nicholas Bieker, Thomas Bläsius, Emil Dohse, and Paul Jungeblut. Recognizing unit disk graphs in hyperbolic geometry is∃R-complete. CoRR, abs/2301.05550, 2023. URL https: //arxiv.org/abs/2301.05550

    work page Pith review arXiv 2023

Show all 55 references
  1. [9]

    https://formal.kastel.kit.edu/teaching/ projektgruppe/themen/WiSe2324/hyperbolicUnitDiskGraphs.pdf, 2023

    Thomas Bläsius and Laura Merker. https://formal.kastel.kit.edu/teaching/ projektgruppe/themen/WiSe2324/hyperbolicUnitDiskGraphs.pdf, 2023

    2023

  2. [10]

    Bodlaender

    Hans L. Bodlaender. A partialk-arboretum of graphs with bounded treewidth.Theoretical Computer Science, 209(1-2):1–45, 1998

    1998

  3. [11]

    Bodlaender, Thomas Wolle, and Arie M

    Hans L. Bodlaender, Thomas Wolle, and Arie M. C. A. Koster. Contraction and treewidth lower bounds. Journal of Graph Algorithms and Applications, 10(1):5–49, 2006

    2006

  4. [12]

    Comparing width parame- ters on graph classes.European Journal of Combinatorics, 127:104163, 2025

    Nick Brettell, Andrea Munaro, Daniël Paulusma, and Shizhou Yang. Comparing width parame- ters on graph classes.European Journal of Combinatorics, 127:104163, 2025

    2025

  5. [13]

    Separating polynomialχ-boundedness from χ-boundedness

    Marcin Briański, James Davies, and Bartosz Walczak. Separating polynomialχ-boundedness from χ-boundedness. Combinatorica, 44:1–8, 2024

    2024

  6. [14]

    Sunil Chandran and C

    L. Sunil Chandran and C. R. Subramanian. Girth and treewidth.Journal of Combinatorial Theory, Series B, 93(1):23–32, 2005

    2005

  7. [15]

    Independent sets in elimination graphs with a submodular objective

    Chandra Chekuri and Kent Quanrud. Independent sets in elimination graphs with a submodular objective. In Nicole Megow and Adam D. Smith, editors,Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023), volume 275 ofLIPIcs, p...

    2023

  8. [16]

    Papadimitriou

    Zhi-Zhong Chen, Michelangelo Grigni, and Christos H. Papadimitriou. Map graphs.Journal of the ACM, 49(2):127–138, 2002

    2002

  9. [17]

    On treewidth and maximum cliques

    Maria Chudnovsky and Nicolas Trotignon. On treewidth and maximum cliques. CoRR, abs/2405.07471, 2024. URL https://arxiv.org/abs/2405.07471

    2024

  10. [18]

    Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh.Parameterized Algorithms

    Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh.Parameterized Algorithms. Springer, 2015

    2015

  11. [19]

    Treewidth versus clique number

    Clément Dallard, Martin Milanič, and Kenny Štorgel. Treewidth versus clique number. II. Tree-independence number. Journal of Combinatorial Theory, Series B, 164:404–442, 2024

    2024

  12. [20]

    Lower bounds for dominating set in ball graphs and for weighted dominating set in unit-ball graphs

    Mark de Berg and Sándor Kisfaludi-Bak. Lower bounds for dominating set in ball graphs and for weighted dominating set in unit-ball graphs. In Fedor V. Fomin, Stefan Kratsch, and Erik Jan van Leeuwen, editors,Treewidth, Kernels, and Algorithms - Essays Dedicated to Hans L. Bodl...

    2020

  13. [21]

    Bodlaender, Sándor Kisfaludi-Bak, Dániel Marx, and Tom C

    Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, Dániel Marx, and Tom C. van der Zanden. A framework for exponential-time-hypothesis–tight algorithms and lower bounds in geometric intersection graphs.SIAM Journal on Computing, 49(6):1291–1331, 2020. 34

    2020

  14. [22]

    Clique- based separators for geometric intersection graphs.Algorithmica, 85(6):1652–1678, 2023

    Mark de Berg, Sándor Kisfaludi-Bak, Morteza Monemizadeh, and Leonidas Theocharous. Clique- based separators for geometric intersection graphs.Algorithmica, 85(6):1652–1678, 2023

    2023

  15. [23]

    Representations by contact and intersection of segments.Algorithmica, 47(4):453–463, 2007

    Hubert de Fraysseix and Patrice Ossona de Mendez. Representations by contact and intersection of segments.Algorithmica, 47(4):453–463, 2007

    2007

  16. [24]

    On contact graphs of paths on a grid

    Zakir Deniz, Esther Galby, Andrea Munaro, and Bernard Ries. On contact graphs of paths on a grid. In Therese Biedl and Andreas Kerren, editors,Graph Drawing and Network Visualization - 26th International Symposium (GD 2018), volume 11282 ofLecture Notes in Computer Science, pa...

    2018

  17. [25]

    A survey of degree-boundedness.European Journal of Combina- torics, page 104092, 2024

    Xiying Du and Rose McCarty. A survey of degree-boundedness.European Journal of Combina- torics, page 104092, 2024. In Press

    2024

  18. [26]

    Vida Dujmović, David Eppstein, and David R. Wood. Structure of graphs with locally restricted crossings. SIAM Journal on Discrete Mathematics, 31(2):805–824, 2017

    2017

  19. [27]

    Vida Dujmović, Pat Morin, and David R. Wood. Layered separators in minor-closed graph classes with applications.Journal of Combinatorial Theory, Series B, 127:111–147, 2017

    2017

  20. [28]

    Vida Dujmović, Louis Esperet, Pat Morin, Bartosz Walczak, and David R. Wood. Clustered 3-colouring graphs of bounded degree.Combinatorics, Probability and Computing, 31(1):123–135, 2022

    2022

  21. [29]

    Vida Dujmović, Pat Morin, and David R. Wood. Graph product structure for non-minor-closed classes. Journal of Combinatorial Theory, Series B, 162:34–67, 2023

    2023

  22. [30]

    Sublinear separators, fragility and subexponential expansion.European Journal of Combinatorics, 52:103–119, 2016

    Zdeněk Dvořák. Sublinear separators, fragility and subexponential expansion.European Journal of Combinatorics, 52:103–119, 2016

    2016

  23. [31]

    Polynomial-time approximation schemes for independent packing problems on fractionally tree-independence-number-fragile graphs

    Esther Galby, Andrea Munaro, and Shizhou Yang. Polynomial-time approximation schemes for independent packing problems on fractionally tree-independence-number-fragile graphs. In Erin W. Chambers and Joachim Gudmundsson, editors,39th International Symposium on Computational Geo...

    2023

  24. [32]

    Polynomial-time approximation schemes for induced subgraph problems on fractionally tree-independence-number-fragile graphs.CoRR, abs/2402.18352, 2024

    Esther Galby, Andrea Munaro, and Shizhou Yang. Polynomial-time approximation schemes for induced subgraph problems on fractionally tree-independence-number-fragile graphs.CoRR, abs/2402.18352, 2024. URL https://arxiv.org/abs/2402.18352

    2024 arXiv

  25. [33]

    Problems from the world surrounding perfect graphs.Zastosowania Matematyki, 19(3-4):413–441, 1987

    András Gyárfás. Problems from the world surrounding perfect graphs.Zastosowania Matematyki, 19(3-4):413–441, 1987

    1987

  26. [34]

    Contact graphs of curves

    Petr Hliněný. Contact graphs of curves. In Franz-Josef Brandenburg, editor,Graph Drawing, Symposium on Graph Drawing (GD ’95), volume 1027 ofLecture Notes in Computer Science, pages 312–323. Springer, 1995

    1995

  27. [35]

    The maximal clique and colourability of curve contact graphs.Discrete Applied Mathematics, 81(1-3):59–68, 1998

    Petr Hliněný. The maximal clique and colourability of curve contact graphs.Discrete Applied Mathematics, 81(1-3):59–68, 1998

    1998

  28. [36]

    Classes and recognition of curve contact graphs.Journal of Combinatorial Theory, Series B, 74(1):87–103, 1998

    Petr Hliněný. Classes and recognition of curve contact graphs.Journal of Combinatorial Theory, Series B, 74(1):87–103, 1998. 35

    1998

  29. [37]

    What graphs are 2-dot product graphs? International Journal of Computational Geometry & Applications, 31(1):1–16, 2021

    Matthew Johnson, Daniël Paulusma, and Erik Jan van Leeuwen. What graphs are 2-dot product graphs? International Journal of Computational Geometry & Applications, 31(1):1–16, 2021

    2021

  30. [38]

    Approximation algorithms for intersection graphs.Algo- rithmica, 68(2):312–336, 2014

    Frank Kammer and Torsten Tholey. Approximation algorithms for intersection graphs.Algo- rithmica, 68(2):312–336, 2014

    2014

  31. [39]

    Hyperbolic intersection graphs and (quasi)-polynomial time

    Sándor Kisfaludi-Bak. Hyperbolic intersection graphs and (quasi)-polynomial time. In Shuchi Chawla, editor,Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA 2020), pages 1621–1638. SIAM, 2020

    2020

  32. [40]

    Coloring powers of chordal graphs.SIAM Journal on Discrete Mathematics, 18(3): 451–461, 2004

    Daniel Král. Coloring powers of chordal graphs.SIAM Journal on Discrete Mathematics, 18(3): 451–461, 2004

    2004

  33. [41]

    Leiserson

    William Kuszmaul and Charles E. Leiserson. Floors and ceilings in divide-and-conquer recur- rences. In Hung Viet Le and Valerie King, editors,4th Symposium on Simplicity in Algorithms (SOSA 2021), pages 133–141. SIAM, 2021

    2021

  34. [42]

    Lee.Riemannian Manifolds: An Introduction to Curvature

    John M. Lee.Riemannian Manifolds: An Introduction to Curvature. Springer, 1997

    1997

  35. [43]

    Lima, Martin Milanič, Peter Muršič, Karolina Okrasa, Paweł Rzążewski, and Kenny Štorgel

    Paloma T. Lima, Martin Milanič, Peter Muršič, Karolina Okrasa, Paweł Rzążewski, and Kenny Štorgel. Tree decompositions meet induced matchings: Beyond Max Weight Independent Set. In Timothy M. Chan, Johannes Fischer, John Iacono, and Grzegorz Herman, editors,32nd Annual Europea...

    2024

  36. [44]

    Bipartizing (pseudo-)disk graphs: Approximation with a ratio better than 3

    Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, and Meirav Zehavi. Bipartizing (pseudo-)disk graphs: Approximation with a ratio better than 3. In Amit Kumar and Noga Ron-Zewi, editors,Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techni...

    2024

  37. [45]

    On a condition for the union of spherical caps to be connected.Journal of Combinatorial Theory, Series A, 101(2):264–270, 2003

    Hiroshi Maehara. On a condition for the union of spherical caps to be connected.Journal of Combinatorial Theory, Series A, 101(2):264–270, 2003

    2003

  38. [46]

    On the intersection graph of random caps on a sphere.European Journal of Combinatorics, 25(5):707–718, 2004

    Hiroshi Maehara. On the intersection graph of random caps on a sphere.European Journal of Combinatorics, 25(5):707–718, 2004

    2004

  39. [47]

    Geometric probability on the sphere.Jahresbericht der Deutschen Mathematiker-Vereinigung, 119:93–132, 2017

    Hiroshi Maehara and Horst Martini. Geometric probability on the sphere.Jahresbericht der Deutschen Mathematiker-Vereinigung, 119:93–132, 2017

    2017

  40. [48]

    Birkhäuser, 2024

    Hiroshi Maehara and Horst Martini.Circles, Spheres and Spherical Geometry. Birkhäuser, 2024

    2024

  41. [49]

    Springer, 2012

    Jaroslav Nešetřil and Patrice Ossona de Mendez.Sparsity - Graphs, Structures, and Algorithms. Springer, 2012

    2012

  42. [50]

    On coloringj-unit sphere graphs

    René Peeters. On coloringj-unit sphere graphs. Technical report, Tilburg University, Department of Economics, 1991

    1991

  43. [51]

    A finite family of pseudodiscs must include a “small” pseudodisc.SIAM Journal on Discrete Mathematics, 28(4):1930–1934, 2014

    Rom Pinchasi. A finite family of pseudodiscs must include a “small” pseudodisc.SIAM Journal on Discrete Mathematics, 28(4):1930–1934, 2014

    1930

  44. [52]

    Richtmyer.Introduction to Hyperbolic Geometry

    Arlan Ramsay and Robert D. Richtmyer.Introduction to Hyperbolic Geometry. Springer, 1995. 36

    1995

  45. [53]

    P. L. Robinson. The sphere is not flat.The American Mathematical Monthly, 113(2):171–173, 2006

    2006

  46. [54]

    A survey ofχ-boundedness

    Alex Scott and Paul Seymour. A survey ofχ-boundedness. Journal of Graph Theory, 95(3): 473–504, 2020

    2020

  47. [55]

    Elimination graphs

    Yuli Ye and Allan Borodin. Elimination graphs. ACM Transactions on Algorithms, 8(2): 14:1–14:23, 2012. 37

    2012

Pith tools

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