Skip to Main content Skip to Navigation
Conference papers

Contraction-Bidimensionality of Geometric Intersection Graphs

Julien Baste 1 Dimitrios M. Thilikos 1, 2
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Given a graph G, we define bcg(G) as the minimum k for which G can be contracted to the uniformly triangulated grid Γ k. A graph class G has the SQGC property if every graph G ∈ G has treewidth O(bcg(G) c) for some 1 ≤ c < 2. The SQGC 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 general family of graph classes that satisfy the SQGC property and includes bounded-degree string graphs. This considerably extends the applicability of bidimensionality theory for several intersection graph classes of 2-dimensional geometrical objects.
Complete list of metadata

Cited literature [43 references]  Display  Hide  Download
Contributor : Dimitrios Thilikos <>
Submitted on : Monday, October 8, 2018 - 4:49:20 PM
Last modification on : Monday, February 1, 2021 - 7:09:20 PM
Long-term archiving on: : Wednesday, January 9, 2019 - 3:21:58 PM


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License




Julien Baste, Dimitrios M. Thilikos. Contraction-Bidimensionality of Geometric Intersection Graphs. 12th International Symposium on Parameterized and Exact Computation (IPEC 2017), Sep 2017, Vienne, Austria. pp.5:1--5:13, ⟨10.4230/LIPIcs.IPEC.2017.5⟩. ⟨lirmm-01890527⟩



Record views


Files downloads