Contraction-bidimensionality of geometric intersection graphs

Julien Baste, Dimitrios M. Thilikos

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 2 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.

Original languageEnglish (US)
Title of host publication12th International Symposium on Parameterized and Exact Computation, IPEC 2017
EditorsDaniel Lokshtanov, Naomi Nishimura
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770514
DOIs
StatePublished - Feb 1 2018
Event12th International Symposium on Parameterized and Exact Computation, IPEC 2017 - Vienna, Austria
Duration: Sep 6 2017Sep 8 2017

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume89
ISSN (Print)1868-8969

Conference

Conference12th International Symposium on Parameterized and Exact Computation, IPEC 2017
Country/TerritoryAustria
CityVienna
Period9/6/179/8/17

Keywords

  • Bidimensionality
  • Geometric intersection graphs
  • Grid exlusion theorem
  • String Graphs

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'Contraction-bidimensionality of geometric intersection graphs'. Together they form a unique fingerprint.

Cite this