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.
Type de document :
Communication dans un congrès
IPEC: International symposium on Parameterized and Exact Computation, Sep 2017, Vienne, Austria. 12th International Symposium on Parameterized and Exact Computation, LIPIcs (89), pp.5:1--5:13, 2017, 〈https://algo2017.ac.tuwien.ac.at/ipec/〉. 〈10.4230/LIPIcs.IPEC.2017.5〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01890527
Contributeur : Dimitrios M. Thilikos <>
Soumis le : lundi 8 octobre 2018 - 16:49:20
Dernière modification le : jeudi 15 novembre 2018 - 18:30:30
Document(s) archivé(s) le : mercredi 9 janvier 2019 - 15:21:58

Fichier

bidicon_IPEC_2017.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Collections

Citation

Julien Baste, Dimitrios M. Thilikos. Contraction-Bidimensionality of Geometric Intersection Graphs. IPEC: International symposium on Parameterized and Exact Computation, Sep 2017, Vienne, Austria. 12th International Symposium on Parameterized and Exact Computation, LIPIcs (89), pp.5:1--5:13, 2017, 〈https://algo2017.ac.tuwien.ac.at/ipec/〉. 〈10.4230/LIPIcs.IPEC.2017.5〉. 〈lirmm-01890527〉

Partager

Métriques

Consultations de la notice

69

Téléchargements de fichiers

8