Contraction Bidimensionality of Geometric Intersection Graphs

DOI10.1007/S00453-021-00912-WMaRDI QIDQ6405521arXivFDO

Authors Julien Baste, Dimitrios M. Thilikos

Publication date 20 July 2022

Published in arXiv

Full work available at URL https://doi.org/10.1007/S00453-021-00912-W

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)

arXiv classification

cs.DMmath.CO

Abstract: Given a graph $G$, we define $$ as the minimum $k$ for which $G$ can be contracted to the uniformly triangulated grid $Gamm{a}_k$. A graph class $calG$ has the SQG$$ property if every graph $GincalG$ has treewidth $$ for some $1leqc<2$. The SQG$$ property is important for algorithm design as it defines the applicability horizon of a series of meta-algorithmic results, in the framework of bidimensionality theory, related to fast parameterized algorithms, kernelization, and approximation schemes. These results apply to a wide family of problems, namely problems that are contraction-bidimensional. Our main combinatorial result reveals a wide family of graph classes that satisfy the SQG$$ property. This family includes, in particular, bounded-degree string graphs. This considerably extends the applicability of bidimensionality theory for contraction bidimensional problems.

This page was built for publication: Contraction Bidimensionality of Geometric Intersection Graphs

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