2022/07/20 by Julien Baste, Baste, Julien, Dimitrios M. Thilikos +1 · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #Computational Geometry and Mesh Generation
paper · pdf · doi:10.48550/arxiv.2207.09751
Given a graph G, we define \bf bcg(G) as the minimum k for which G can be contracted to the uniformly triangulated grid Γk. A graph class \cal G has the SQG\bf C property if every graph G∈\cal G has treewidth O(\bf bcg(G)c) for some 1≤ c<2. The SQG\bf C 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\bf C property. This family includes, in particular, bounded-degree string graphs. This considerably extends the applicability of bidimensionality theory for contraction bidimensional problems.