On Supports for Graphs of Bounded Genus

Rajiv Raman, Karamjeet Singh · 2025

Read On Supports for Graphs of Bounded Genus by Rajiv Raman, Karamjeet Singh (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-21287.txt.

Introduction

Rajiv Raman and Karamjeet Singh wrote a 2025 mathematics paper on when a network of linked sets, a hypergraph, can be drawn as one ordinary graph, called a support. Each set must appear as one connected blob in the graph. The sets here come from connected parts of a host graph. The vertices of the host are split into key vertices, called terminals, and plain vertices. A twin setup flips the roles, with each key vertex defining a set.

The team works on a merged framework that covers both setups. Their main result concerns host graphs on surfaces with few holes, of bounded genus. When the parts cross in a tame, cross-free way, a support graph can be built. It sits on such a surface too. The work extends an earlier flat-case result to curved surfaces. It also feeds packing and covering problems on such graphs.

Catalog record

CREATORRajiv Raman, Karamjeet Singh
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE132 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-21287

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On Supports for Graphs of Bounded Genus Thanks: A preliminary version of these results appeared in EUROCOMB’23 Raman and Singh (2023) . Rajiv Raman, Karamjeet Singh Abstract Let ( X , ℰ ) (X,\mathcal{E}) be a hypergraph. A support is a graph Q Q on X X such that for each E ∈ ℰ E\in\mathcal{E} , the subgraph of Q Q induced on the elements in E E is connected. We consider hypergraphs defined by connected subgraphs of a host graph. For a graph G = ( V , E ) G=(V,E) , let 𝐛 ⁡ ( V ) ⊆ V \mathbf{b}(V)\subseteq V denote a set of terminals . Given a collection ℋ \mathcal{H} of connected subgraphs of G G , we define a hypergraph on 𝐛 ⁡ ( V ) \mathbf{b}(V) , where each H ∈ ℋ H\in\mathcal{H} defines a hyperedge V ⁡ ( H ) ∩ 𝐛 ⁡ ( V ) V(H)\cap\mathbf{b}(V) . Our goal is to construct a graph Q Q on 𝐛 ⁡ ( V ) \mathbf{b}(V) so that for each H ∈ ℋ H\in\mathcal{H} , V ⁡ ( H ) ∩ 𝐛 ⁡ ( V ) V(H)\cap\mathbf{b}(V) induces a connected subgraph of Q Q . We also consider the problem of constructing a support for the dual hypergraph - a hypergraph on ℋ \mathcal{H} where each v ∈ 𝐛 ⁡ ( V ) v\in\mathbf{b}(V) defines a hyperedge consisting of the subgraphs in ℋ \mathcal{H} containing v v . In fact, we construct supports for a common generalization of the primal and dual settings called the intersection hypergraph . As our main result, we show that if the host graph G G has genus g g and the subgraphs in ℋ \mathcal{H} satisfy a condition of being cross-free , then there exists a support that also has genus at most g g . 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)) and our techniques extend their results from the planar setting to graphs on surfaces. In particular, 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. \declaretheorem [name=Lemma,numberlike=lemma]lem \declaretheorem [name=Theorem,numberlike=theorem]thm \declaretheorem [name=Corollary,numberlike=theorem]cor † † dmtcs-publicationdata: Volume vol. 28:2 (2026), #28, doi:10.46298/dmtcs.16086 1 Introduction A hypergraph (X,\mathcal{E}) consists of a set X and a collection \mathcal{E} of subsets of X called hyperedges . Hypergraphs generalize graphs (where \mathcal{E} consists only of 2-element subsets of X ). We are interested in questions of representing hypergraphs by sparse graphs that capture some of its structure. The notion of structure we want to preserve is that of connectedness of the hyperedges. Consider a hypergraph (X,\mathcal{E}) . A graph Q on X is a support for the hypergraph if for each E\in\mathcal{E} , the induced graph Q[E] of Q is connected. If we ignore the sparsity, we can trivially construct a support by taking a complete graph on X . The problems become non-trivial if we impose sparsity. For example, if we require the support graph to be planar, then even deciding if a hypergraph admits such a support is NP-hard due to a result of Johnson and Pollak (1987) . The notion of a support was introduced by Voloshina and Feinberg (1984) in the context of VLSI circuits (see Feinberg et al. (1997a) for an English version), and has since been rediscovered by several communities. For example, the existence and construction of sparse supports arises naturally in the problem of visualizing hypergraphs, see Bereg et al. (2015) ; Bereg et al. (2011) ; Brandes et al. (2011) ; Brandes et al. (2012) ; Buchin et al. (2011) ; Havet et al. (2022) ; Hurtado et al. (2018) , and in the design of networks, see Chen et al. (2015) ; Hosoda et al. (2012) ; Korach and Stern (2003) ; Onus and Richa (2011) . Since it is already NP-hard to decide if a hypergraph admits a support that is a planar graph, it is natural to consider restricted settings that ensure the existence of a sparse support. Raman and Ray (2020) considered hypergraphs defined by non-piercing regions 1 1 1 A slightly imprecise definition is the following: a family \mathcal{R} of path connected regions in the plane or on an oriented surface such that for any two regions R,R^{\prime}\in\mathcal{R} , the regions R\setminus R^{\prime} and R^{\prime}\setminus R are also connected are called non-piercing regions. They include disks, pseudodisks, unit height-axis parallel rectangles, etc. See Def. 4.10 . in the plane (see Section 7.2 for a definition of these hypergraphs). The authors showed the existence of planar primal, dual and intersection supports for these hypergraphs. In Raman and Ray (2020) , the authors were motivated by the analysis of algorithms for Packing and Covering problems for hypergraphs defined by geometric regions in the plane. Several such problems admit PTAS via algorithms from a basic local-search framework. To show that the algorithms in this framework are a PTAS requires showing the existence of a local-search graph . The existence of a support in many cases directly implies the existence of such a local-search graph (though in some cases, some extra work is required). We introduce the notion of hypergraphs defined by connected subgraphs of a host graph. This yields a cleaner combinatorial model to study the geometric hypergraphs considered in Raman and Ray (2020) . To see this, consider an arrangement of disks in the plane. The dual arrangement graph G corresponding to the disks is a plane graph that has a vertex for each cell of the arrangement, and two vertices in G are adjacent if and only if the corresponding cells are separated by the boundary of a disk. Each disk then defines a connected subgraph of G - the subgraph induced on the cells contained in that disk. The subgraphs defined by any pair of disks are non-piercing in the graph-theoretic sense. That is, if G is the dual arrangement graph of a set of disks, and A and B are two subgraphs of G corresponding to disks R_{A} and R_{B} respectively, then the induced subgraphs on V(A)\setminus V(B) and V(B)\setminus V(A) are connected subgraphs of G . If we are given a set P of points and a set D of disks, this defines a hypergraph (P,\mathcal{D}) on P where each D\in\mathcal{D} defines a hyperedge D\cap P . For each cell containing a point of P , we choose a representative point of P from this cell as its representative vertex, and assign it a color blue . Otherwise, the vertex corresponding to the cell is colored red . A planar support for the hypergraph defined by blue vertices and disks then easily yields a planar support for the hypergraph (P,\mathcal{D}) . See Fig. 1 for the construction of a graph and a support. This approach enables the study of geometric hypergraphs entirely within a graph-theoretic framework. (a) Disks and Points (b) Dual arrangement graph (c) Support on blue points for hypergraph in (b) (d) Support for the hypergraph defined in (a) Figure 1: Support for hypergraph

Read the complete text