On the Pathwidth of Planar Graphs

Omid Amini 1 Florian Huc 1 Stéphane Pérennes 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 : Fomin and Thilikos in [5] conjectured that there is a constant $c$ such that, for every $2$-connected planar graph $G$, {pw}(G^*) \leq 2\text{pw}(G)+c$ (the same question was asked simutaneously by Coudert, Huc and Sereni in [4]). By the results of Boedlander and Fomin [2] this holds for every outerplanar graph and actually is tight by Coudert, Huc and Sereni [4]. In [5], Fomin and Thilikos proved that there is a constant $c$ such that the pathwidth of every 3-connected graph $G$ satisfies: ${pw}(G^*) \leq 6\text{pw}(G)+c$. In this paper we improve this result by showing that the dual a 3-connected planar graph has pathwidth at most $3$ times the pathwidth of the primal plus two. We prove also that the question can be answered positively for $4$-connected planar graphs.
Type de document :
[Research Report] 2006, pp.6
Liste complète des métadonnées

Contributeur : Omid Amini <>
Soumis le : vendredi 7 juillet 2006 - 15:56:20
Dernière modification le : mercredi 31 janvier 2018 - 10:24:04
Document(s) archivé(s) le : lundi 5 avril 2010 - 23:25:28



  • HAL Id : inria-00082035, version 1



Omid Amini, Florian Huc, Stéphane Pérennes. On the Pathwidth of Planar Graphs. [Research Report] 2006, pp.6. 〈inria-00082035〉



Consultations de la notice


Téléchargements de fichiers