Pathwidth of outerplanar graphs

David Coudert 1 Florian Huc 1 Jean-Sébastien Sereni 1
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : We are interested in the relation between the pathwidth of a biconnected outerplanar graph and the pathwidth of its (geometric) dual. Bodlaender and Fomin [3], after having proved that the pathwidth of every biconnected outerplanar graph is always at most twice the pathwidth of its (geometric) dual plus two, conjectured that there exists a constant c such that the pathwidth of every biconnected outerplanar graph is at most c plus the pathwidth of its dual. They also conjectured that this was actually true with c being one for every biconnected planar graph. Fomin [10] proved that the second conjecture is true for all planar triangulations. First, we construct for each p 1, a biconnected outerplanar graph of pathwidth 2p + 1 whose (geometric) dual has pathwidth p + 1, thereby disproving both conjectures. Next, we also disprove two other conjectures (one of Bodlaender and Fomin [3], implied by one of Fomin [10]. Finally we prove, in an algorithmic way, that the pathwidth of every biconnected outerplanar graph is at most twice the pathwidth of its (geometric) dual minus one. A tight interval for the studied relation is therefore obtained, and we show that all cases in the interval happen.
Type de document :
Article dans une revue
Journal of Graph Theory, Wiley, 2007, 55 (1), pp.27 - 41. 〈10.1002/jgt.20218〉
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00429216
Contributeur : David Coudert <>
Soumis le : dimanche 1 novembre 2009 - 21:30:25
Dernière modification le : lundi 4 décembre 2017 - 15:14:09
Document(s) archivé(s) le : jeudi 17 juin 2010 - 18:59:07

Fichier

CHS-JGT06.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

David Coudert, Florian Huc, Jean-Sébastien Sereni. Pathwidth of outerplanar graphs. Journal of Graph Theory, Wiley, 2007, 55 (1), pp.27 - 41. 〈10.1002/jgt.20218〉. 〈inria-00429216〉

Partager

Métriques

Consultations de la notice

235

Téléchargements de fichiers

128