Bidimensionality of geometric intersection graphs

DOI10.1007/978-3-319-04298-5_26MaRDI QIDQ2938107zbMATH OpenOpenAlexFDO

Authors Alexander Grigoriev, Athanassios Koutsonas, Dimitrios M. Thilikos

Publication date 13 January 2015

Published in SOFSEM 2014: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1308.6166

zbMATH Keywords

bidimensionalitygeometric intersection graphsgrid exlusion theorem

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: Let B be a finite collection of geometric (not necessarily convex) bodies in the plane. Clearly, this class of geometric objects naturally generalizes the class of disks, lines, ellipsoids, and even convex polygons. We consider geometric intersection graphs GB where each body of the collection B is represented by a vertex, and two vertices of GB are adjacent if the intersection of the corresponding bodies is non-empty. For such graph classes and under natural restrictions on their maximum degree or subgraph exclusion, we prove that the relation between their treewidth and the maximum size of a grid minor is linear. These combinatorial results vastly extend the applicability of all the meta-algorithmic results of the bidimensionality theory to geometrically defined graph classes.

Recommendations

• Contraction-bidimensionality of geometric intersection graphs
• scientific article; zbMATH DE number 7053376
• Contraction bidimensionality of geometric intersection graphs
• Mathematical Foundations of Computer Science 2004
• The Bidimensional Theory of Bounded-Genus Graphs

Cited in

(8)

• Bidimensionality and kernels
• Testing bipartiteness of geometric intersection graphs
• Coverability and sub-exponential parameterized algorithms in planar graphs
• A Retrospective on (Meta) Kernelization
• Contraction-bidimensionality of geometric intersection graphs
• scientific article; zbMATH DE number 7053376 (Why is no real title available?)
• Subexponential algorithms in geometric graphs via the subquadratic grid minor property: the role of local radius
• Contraction bidimensionality of geometric intersection graphs

This page was built for publication: Bidimensionality of geometric intersection graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2938107)