2026-07-21T10:22:51Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8548 2024-03-06T10:41:29Z ddc:004 open_access

Contraction-Bidimensionality of Geometric Intersection Graphs Baste, Julien Thilikos, Dimitrios M. Grid exlusion theorem Bidimensionality Geometric intersection graphs String Graphs Given a graph G, we define bcg(G) as the minimum k for which G can be contracted to the uniformly triangulated grid Gamma_k. A graph class G has the SQGC property if every graph G in 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Julien Baste and Dimitrios M. Thilikos 2018 Is Part Of LIPIcs, Volume 89, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2017.5 urn:nbn:de:0030-drops-85487 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.5 eng https://creativecommons.org/licenses/by/3.0/legalcode