pith. sign in

arxiv: 2503.21287 · v6 · pith:N524EY5Ynew · submitted 2025-03-27 · 🧮 math.CO · cs.DM

On Supports for graphs of bounded genus

Rajiv Raman , Karamjeet Singh This is my paper

Pith reviewed 2026-05-22 23:17 UTC · model grok-4.3

classification 🧮 math.CO cs.DM
keywords supportsbounded genuscross-free subgraphsintersection hypergraphhypergraph coloringpacking and coveringgraph embeddings
0
0 comments X

The pith

If a host graph has bounded genus and its connected subgraphs are cross-free, then a support of bounded genus exists.

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

The paper shows that a support graph for the hypergraph formed by terminals in a collection of connected subgraphs can be chosen with bounded genus whenever the host graph has bounded genus and the subgraphs meet the cross-free condition. This construction covers the primal hypergraph on terminals, the dual hypergraph on the subgraphs, and their intersection hypergraph generalization. The result extends prior work that handled only the planar case and supplies a common method for analyzing packing and covering questions on surfaces. It also yields consequences for coloring the resulting hypergraphs.

Core claim

If the host graph G has bounded genus and the subgraphs in H are cross-free, then there exists a support Q that also has bounded genus. The support is built for the intersection hypergraph whose vertices are the terminals b(V) and whose hyperedges record the terminals lying inside each member of H. The same genus bound holds for the primal and dual special cases of this hypergraph.

What carries the argument

The intersection hypergraph on terminals and cross-free subgraphs of the host, whose support is required to induce a connected subgraph on each hyperedge.

If this is right

  • The genus bound transfers to supports of both the primal hypergraph on terminals and the dual hypergraph on subgraphs.
  • Packing and covering problems for these hypergraphs on bounded-genus surfaces admit a unified treatment via the support.
  • Hypergraph coloring results follow directly from the existence of the low-genus support.

Where Pith is reading between the lines

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

  • The same reduction may apply to other topological measures such as Euler genus or orientability when the cross-free condition is preserved.
  • Algorithmic consequences for Steiner-type problems on surfaces could follow if the support construction is made polynomial-time.
  • The approach might combine with existing surface embedding algorithms to produce explicit drawings of the support.

Load-bearing premise

The subgraphs in H satisfy the cross-free condition.

What would settle it

An explicit bounded-genus host graph together with a cross-free family of connected subgraphs for which every support has genus larger than any fixed bound.

Figures

Figures reproduced from arXiv: 2503.21287 by Karamjeet Singh, Rajiv Raman.

Figure 1
Figure 1. Figure 1: Support for hypergraph defined by disks and points in the plane. [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: (a) and (b): Primal and Dual hypergraphs on the graph system [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Vertex Bypassing [PITH_FULL_IMAGE:figures/full_fig_p017_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Finding a non-blocking chord to join two disjoint runs of [PITH_FULL_IMAGE:figures/full_fig_p022_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: An arrangement of Pseudodisks (left), Piercing (middle), and Non [PITH_FULL_IMAGE:figures/full_fig_p046_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: The subgraphs A colored orange, B colored green, and C colored blue are touching. Observe that A \ B is connected, while B \ A induces two connected components. There is an input point on the boundary of the three regions. The regions are weakly non-piercing, but are not non-piercing. Let R be a collection of weakly non-piercing regions on a surface of genus g. Consider the boundaries ∂R and ∂R′ of two reg… view at source ↗
Figure 7
Figure 7. Figure 7: Construction of cross-free graph system for simply connected re [PITH_FULL_IMAGE:figures/full_fig_p049_7.png] view at source ↗
read the original abstract

Let $(X,\mathcal{E})$ be a hypergraph. A support is a graph $Q$ on $X$ such that for each $E\in\mathcal{E}$, the subgraph of $Q$ induced on the elements in $E$ is connected. We consider the problem of constructing a support for hypergraphs defined by connected subgraphs of a host graph. For a graph $G=(V,E)$, let $\mathcal{H}$ be a set of connected subgraphs of $G$. Let the vertices of $G$ be partitioned into two sets the \emph{terminals} $\mathbf{b}(V)$ and the \emph{non-terminals} $\mathbf{r}(V)$. We define a hypergraph on $\mathbf{b}(V)$, where each $H\in\mathcal{H}$ defines a hyperedge consisting of the vertices of $\mathbf{b}(V)$ in $H$. We also consider the problem of constructing a support for the \emph{dual hypergraph} - a hypergraph on $\mathcal{H}$ where each $v\in \mathbf{b}(V)$ defines a hyperedge consisting of the subgraphs in $\mathcal{H}$ containing $v$. In fact, we construct supports for a common generalization of the primal and dual settings called the \emph{intersection hypergraph}. As our main result, we show that if the host graph $G$ has bounded genus and the subgraphs in $\mathcal{H}$ satisfy a condition of being \emph{cross-free}, then there exists a support that also has bounded genus. Our results are a generalization of the results of Raman and Ray (Rajiv Raman, Saurabh Ray: Constructing Planar Support for Non-Piercing Regions. Discret. Comput. Geom. 64(3): 1098-1122 (2020)). Our techniques imply a unified analysis for packing and covering problems for hypergraphs defined on surfaces of bounded genus. We also describe applications of our results for hypergraph colorings.

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

0 major / 2 minor

Summary. The paper studies supports for hypergraphs whose hyperedges arise as the terminal vertices in connected subgraphs of a host graph G. It defines the primal hypergraph on terminals, the dual on the subgraphs, and their common generalization (the intersection hypergraph). The main theorem states that when G has bounded genus and the family H of subgraphs is cross-free, a support of bounded genus exists; this is presented as a direct generalization of the planar non-piercing result of Raman and Ray. The authors also derive consequences for packing/covering problems and hypergraph coloring on bounded-genus surfaces.

Significance. If the central existence result holds, the work supplies a uniform bounded-genus support construction that unifies packing and covering arguments on surfaces and extends the planar theory in a natural way. The cross-free hypothesis is explicitly flagged as the necessary generalization of non-piercing, and the applications to coloring are concrete.

minor comments (2)
  1. [§1] §1 (Introduction): the precise definition of 'cross-free' is invoked in the main theorem but is only sketched; a self-contained formal definition with a small illustrative figure would help readers verify that it correctly generalizes the non-piercing condition.
  2. [Main theorem] The statement of the main theorem (presumably Theorem 1 or equivalent) should explicitly record the genus bound in terms of the genus of G and the cross-free parameter, even if the bound is not tight.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, recognition of the significance of the bounded-genus support result, and recommendation of minor revision. The report does not list any specific major comments under the MAJOR COMMENTS section.

Circularity Check

0 steps flagged

No significant circularity; existence theorem is conditional on explicit assumption and generalizes independent prior result

full rationale

The paper states an existence theorem: if host graph G has bounded genus and the family H of connected subgraphs satisfies the explicitly named cross-free condition, then a bounded-genus support exists for the associated intersection hypergraph. This is presented as a direct generalization of the planar non-piercing case from the cited Raman-Ray 2020 paper. No equations, fitted parameters, statistical predictions, or ansatzes appear in the abstract or theorem statement. The cross-free condition is flagged as a hypothesis rather than derived from the result itself. The self-citation serves only to identify the prior result being extended and does not function as a load-bearing justification or uniqueness theorem inside the current derivation. The claim therefore remains an independent conditional existence statement with no reduction to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Abstract-only review yields no explicit free parameters, invented entities, or non-standard axioms; the result rests on standard definitions of genus, connectedness, and cross-freeness from prior literature.

axioms (1)
  • standard math Standard topological properties of graph genus and induced connectedness on surfaces.
    Used to define the host graph G of bounded genus and the connected subgraphs in H.

pith-pipeline@v0.9.0 · 5892 in / 1084 out tokens · 81479 ms · 2026-05-22T23:17:20.153900+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

47 extracted references · 47 canonical work pages · 1 internal anchor

  1. [1]

    Coloring hy- pergraphs defined by stabbed pseudo-disks and abab-free hypergraphs

    Eyal Ackerman, Bal´ azs Keszegh, and D¨ om¨ ot¨ or P´ alv¨ olgyi. Coloring hy- pergraphs defined by stabbed pseudo-disks and abab-free hypergraphs. SIAM Journal on Discrete Mathematics, 34(4):2250–2269, 2020

    work page 2020

  2. [2]

    A separator theorem for nonplanar graphs.Journal of the American Mathematical Society, 3(4):801–808, 1990

    Noga Alon, Paul Seymour, and Robin Thomas. A separator theorem for nonplanar graphs.Journal of the American Mathematical Society, 3(4):801–808, 1990

    work page 1990

  3. [3]

    Katz, Gila Morgenstern, and Yelena Yudit- sky

    Rom Aschner, Matthew J. Katz, Gila Morgenstern, and Yelena Yudit- sky. Approximation schemes for covering and packing. In Subir Ku- mar Ghosh and Takeshi Tokuyama, editors,WALCOM: Algorithms and Computation, 7th International Workshop, WALCOM 2013, Kharag- pur, India, February 14-16, 2013. Proceedings, volume 7748 ofLec- ture Notes in Computer Science, pa...

    work page doi:10.1007/978-3-642-36065-7 2013

  4. [4]

    Tera: topic-based event routing for peer- to-peer architectures

    Roberto Baldoni, Roberto Beraldi, Vivien Quema, Leonardo Querzoni, and Sara Tucci-Piergiovanni. Tera: topic-based event routing for peer- to-peer architectures. InProceedings of the 2007 inaugural international conference on Distributed event-based systems, pages 2–13, 2007

    work page 2007

  5. [5]

    Effectiveness of local search for art gallery problems

    Sayan Bandyapadhyay and Aniket Basu Roy. Effectiveness of local search for art gallery problems. In Faith Ellen, Antonina Kolokolova, and J¨ org-R¨ udiger Sack, editors,Algorithms and Data Structures - 15th International Symposium, WADS 2017, St. John’s, NL, Canada, July 31 - August 2, 2017, Proceedings, volume 10389 ofLecture Notes in Computer Science, p...

    work page 2017

  6. [6]

    Minimum ver- tex cover in rectangle graphs.Computational Geometry, 44(6-7):356– 364, 2011

    Reuven Bar-Yehuda, Danny Hermelin, and Dror Rawitz. Minimum ver- tex cover in rectangle graphs.Computational Geometry, 44(6-7):356– 364, 2011

    work page 2011

  7. [7]

    Packing and covering with non-piercing regions.Discrete & Com- putational Geometry, 2018

    Aniket Basu Roy, Sathish Govindarajan, Rajiv Raman, and Saurabh Ray. Packing and covering with non-piercing regions.Discrete & Com- putational Geometry, 2018. 52

    work page 2018

  8. [8]

    Colored non-crossing Eu- clidean Steiner forest

    Sergey Bereg, Krzysztof Fleszar, Philipp Kindermann, Sergey Pupyrev, Joachim Spoerhase, and Alexander Wolff. Colored non-crossing Eu- clidean Steiner forest. InAlgorithms and Computation: 26th Interna- tional Symposium, ISAAC 2015, Nagoya, Japan, December 9-11, 2015, Proceedings, pages 429–441. Springer, 2015

    work page 2015

  9. [9]

    On the red/blue spanning tree problem.Theoretical computer science, 412(23):2459–2467, 2011

    Sergey Bereg, Minghui Jiang, Boting Yang, and Binhai Zhu. On the red/blue spanning tree problem.Theoretical computer science, 412(23):2459–2467, 2011

    work page 2011

  10. [10]

    Blocks of hypergraphs: applied to hypergraphs and outer- planarity

    Ulrik Brandes, Sabine Cornelsen, Barbara Pampel, and Arnaud Sal- laberry. Blocks of hypergraphs: applied to hypergraphs and outer- planarity. InCombinatorial Algorithms: 21st International Workshop, IWOCA 2010, London, UK, July 26-28, 2010, Revised Selected Papers 21, pages 201–211. Springer, 2011

    work page 2010

  11. [11]

    Path-based supports for hypergraphs.Journal of Discrete Al- gorithms, 14:248–261, 2012

    Ulrik Brandes, Sabine Cornelsen, Barbara Pampel, and Arnaud Sal- laberry. Path-based supports for hypergraphs.Journal of Discrete Al- gorithms, 14:248–261, 2012

    work page 2012

  12. [12]

    On planar supports for hypergraphs.Journal of Graph Algorithms and Applications, 15(4):533–549, 2011

    Kevin Buchin, Marc J van Kreveld, Henk Meijer, Bettina Speckmann, and KAB Verbeek. On planar supports for hypergraphs.Journal of Graph Algorithms and Applications, 15(4):533–549, 2011

    work page 2011

  13. [13]

    Simple PTAS's for families of graphs excluding a minor

    Sergio Cabello and David Gajser. Simple PTAS’s for families of graphs excluding a minor.CoRR, abs/1410.5778, 2014

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  14. [14]

    Chan and Elyot Grant

    Timothy M. Chan and Elyot Grant. Exact algorithms and APX- hardness results for geometric packing and covering problems.Comput. Geom., 47(2):112–124, 2014.doi:10.1016/j.comgeo.2012.04.001

    work page doi:10.1016/j.comgeo.2012.04.001 2014

  15. [15]

    Approximation Algorithms for Maxi mum Independent Set of Pseudo-Disks

    Timothy M. Chan and Sariel Har-Peled. Approximation algorithms for maximum independent set of pseudo-disks.Discrete & Computational Geometry, 48(2):373–392, 2012.doi:10.1007/s00454-012-9417-5

    work page doi:10.1007/s00454-012-9417-5 2012

  16. [16]

    Polynomial-time data reduction for the subset interconnection design problem.SIAM Journal on Discrete Mathematics, 29(1):1–25, 2015

    Jiehua Chen, Christian Komusiewicz, Rolf Niedermeier, Manuel Sorge, Ondrej Suchy, and Mathias Weller. Polynomial-time data reduction for the subset interconnection design problem.SIAM Journal on Discrete Mathematics, 29(1):1–25, 2015. 53

    work page 2015

  17. [17]

    A greedy heuristic for the set-covering problem.Math- ematics of operations research, 4(3):233–235, 1979

    Vasek Chvatal. A greedy heuristic for the set-covering problem.Math- ematics of operations research, 4(3):233–235, 1979

    work page 1979

  18. [18]

    Applications of random sam- pling in computational geometry, ii.Discrete & Computational Geome- try, 4(5):387–421, 1989

    Kenneth L Clarkson and Peter W Shor. Applications of random sam- pling in computational geometry, ii.Discrete & Computational Geome- try, 4(5):387–421, 1989

    work page 1989

  19. [19]

    Sweeping arrangements of non-piercing regions in the plane

    Suryendu Dalal, Rahul Gangopadhyay, Rajiv Raman, and Saurabh Ray. Sweeping arrangements of non-piercing regions in the plane. In Wolf- gang Mulzer and Jeff M. Phillips, editors,40th International Symposium on Computational Geometry, SoCG 2024, June 11-14, 2024, Athens, Greece, volume 293 ofLIPIcs, pages 45:1–45:15. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur...

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

  20. [20]

    Graph theory 3rd ed.Graduate texts in mathematics, 173(33):12, 2005

    Reinhard Diestel. Graph theory 3rd ed.Graduate texts in mathematics, 173(33):12, 2005

    work page 2005

  21. [21]

    A threshold of ln n for approximating set cover.Journal of the ACM (JACM), 45(4):634–652, 1998

    Uriel Feige. A threshold of ln n for approximating set cover.Journal of the ACM (JACM), 45(4):634–652, 1998

    work page 1998

  22. [22]

    Springer Science & Business Media, 2012

    VZ Feinberg, AG Levin, and EB Rabinovich.VLSI planarization: meth- ods, models, implementation, volume 399. Springer Science & Business Media, 2012

    work page 2012

  23. [23]

    A sep- arator theorem for graphs of bounded genus.Journal of Algorithms, 5(3):391–407, 1984

    John R Gilbert, Joan P Hutchinson, and Robert Endre Tarjan. A sep- arator theorem for graphs of bounded genus.Journal of Algorithms, 5(3):391–407, 1984

    work page 1984

  24. [24]

    Overlaying a hypergraph with a graph with bounded maximum degree

    Fr´ ed´ eric Havet, Dorian Mazauric, Viet-Ha Nguyen, and R´ emi Watrigant. Overlaying a hypergraph with a graph with bounded maximum degree. Discrete Applied Mathematics, 319:394–406, 2022

    work page 2022

  25. [25]

    On the approximability and hardness of minimum topic connected overlay and its special instances.Theoretical Computer Science, 429:144–154, 2012

    Jun Hosoda, Juraj Hromkoviˇ c, Taisuke Izumi, Hirotaka Ono, Monika Steinov´ a, and Koichi Wada. On the approximability and hardness of minimum topic connected overlay and its special instances.Theoretical Computer Science, 429:144–154, 2012

    work page 2012

  26. [26]

    Clique is hard to approximate withinn1−ε.Acta Mathematica, 182(1):105–142, 1999

    J H˚ astad. Clique is hard to approximate withinn1−ε.Acta Mathematica, 182(1):105–142, 1999. 54

    work page 1999

  27. [27]

    Colored spanning graphs for set visual- ization.Computational Geometry, 68:262–276, 2018

    Ferran Hurtado, Matias Korman, Marc van Kreveld, Maarten L¨ offler, Vera Sacrist´ an, Akiyoshi Shioura, Rodrigo I Silveira, Bettina Speck- mann, and Takeshi Tokuyama. Colored spanning graphs for set visual- ization.Computational Geometry, 68:262–276, 2018

    work page 2018

  28. [28]

    Hypergraph planarity and the complexity of drawing venn diagrams.Journal of graph theory, 11(3):309–325, 1987

    David S Johnson and Henry O Pollak. Hypergraph planarity and the complexity of drawing venn diagrams.Journal of graph theory, 11(3):309–325, 1987

    work page 1987

  29. [29]

    Conflict-free coloring of inter- section graphs of geometric objects

    Chaya Keller and Shakhar Smorodinsky. Conflict-free coloring of inter- section graphs of geometric objects. InProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 2397–2411, 2018

    work page 2018

  30. [30]

    Coloring intersection hypergraphs of pseudo- disks.Discret

    Bal´ azs Keszegh. Coloring intersection hypergraphs of pseudo- disks.Discret. Comput. Geom., 64(3):942–964, 2020.doi:10.1007/ s00454-019-00142-6

    work page 2020

  31. [31]

    The clustering matroid and the optimal clustering tree.Mathematical Programming, 98:385–414, 2003

    Ephraim Korach and Michal Stern. The clustering matroid and the optimal clustering tree.Mathematical Programming, 98:385–414, 2003

    work page 2003

  32. [32]

    Guarding terrains via local search.Journal of Computational Geometry, 5(1):168–178, 2014

    Erik Krohn, Matt Gibson, Gaurav Kanade, and Kasturi Varadarajan. Guarding terrains via local search.Journal of Computational Geometry, 5(1):168–178, 2014

    work page 2014

  33. [33]

    On the ratio of optimal integral and fractional covers

    Laszlo Lov´ asz. On the ratio of optimal integral and fractional covers. Discrete Math, 13:383390, 1975

    work page 1975

  34. [34]

    Graphs on surfaces

    Bojan Mohar and Carsten Thomassen. Graphs on surfaces. InJohns Hopkins series in the mathematical sciences, 2001. URL:https://api. semanticscholar.org/CorpusID:27349785

    work page 2001

  35. [35]

    Mustafa, Rajiv Raman, and Saurabh Ray

    Nabil H. Mustafa, Rajiv Raman, and Saurabh Ray. Quasi-polynomial time approximation scheme for weighted geometric set cover on pseu- dodisks and halfspaces.SIAM Journal on Computing, 44(6):1650–1669, 2015

    work page 2015

  36. [36]

    Improved results on geometric hit- ting set problems.Discrete & Computational Geometry, 44(4):883–895, 2010

    Nabil H Mustafa and Saurabh Ray. Improved results on geometric hit- ting set problems.Discrete & Computational Geometry, 44(4):883–895, 2010. 55

    work page 2010

  37. [37]

    Vertex packings: struc- tural properties and algorithms.Mathematical Programming, 8(1):232– 248, 1975

    George L Nemhauser and Leslie E Trotter Jr. Vertex packings: struc- tural properties and algorithms.Mathematical Programming, 8(1):232– 248, 1975

    work page 1975

  38. [38]

    Minimum maximum-degree publish– subscribe overlay network design.IEEE/ACM Transactions on Net- working, 19(5):1331–1343, 2011

    Melih Onus and Andr´ ea W Richa. Minimum maximum-degree publish– subscribe overlay network design.IEEE/ACM Transactions on Net- working, 19(5):1331–1343, 2011

    work page 2011

  39. [39]

    Constructing planar support for non- piercing regions.Discrete & Computational Geometry, 64(3):1098–1122, 2020

    Rajiv Raman and Saurabh Ray. Constructing planar support for non- piercing regions.Discrete & Computational Geometry, 64(3):1098–1122, 2020

    work page 2020

  40. [40]

    On the geometric set multicover prob- lem.Discret

    Rajiv Raman and Saurabh Ray. On the geometric set multicover prob- lem.Discret. Comput. Geom., 68(2):566–591, 2022.doi:10.1007/ s00454-022-00402-y

    work page 2022

  41. [41]

    On hypergraph supports

    Rajiv Raman and Karamjeet Singh. On hypergraph supports. InPro- ceedings of the 12th European Conference on Combinatorics, Graph The- ory and Applications (EUROCOMB’23), 2023.doi:10.5817/CZ.MUNI. EUROCOMB23-107

    work page doi:10.5817/cz.muni 2023

  42. [42]

    The clarkson–shor technique revisited and extended

    Micha Sharir. The clarkson–shor technique revisited and extended. Combinatorics, Probability and Computing, 12(2):191–201, 2003

    work page 2003

  43. [43]

    Robert E Tarjan and Mihalis Yannakakis. Simple linear-time algo- rithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs.SIAM Journal on computing, 13(3):566–579, 1984

    work page 1984

  44. [44]

    Planarity of hypergraphs

    AA Voloshina and VZ Feinberg. Planarity of hypergraphs. InDOK- LADY AKADEMII NAUK BELARUSI, volume 28, pages 309–311. ACADEMII NAUK BELARUSI F SCORINA PR 66, ROOM 403, MINSK, BYELARUS 220072, 1984

    work page 1984

  45. [45]

    Torus grid graph.https://mathworld

    Eric W Weisstein. Torus grid graph.https://mathworld. wolfram. com/, 2016

    work page 2016

  46. [46]

    McGill University, School of Computer Science, 1990

    Sue Whitesides and Rongyao Zhao.K-admissible collections of Jordan curves and offsets of circular arc figures. McGill University, School of Computer Science, 1990. 56

    work page 1990

  47. [47]

    Hypergraphs.Russian Mathematical Surveys, 29(6):89, 1974

    Alexander Aleksandrovich Zykov. Hypergraphs.Russian Mathematical Surveys, 29(6):89, 1974. 57

    work page 1974