2009/01/01 by Omid Amini, Florian Huc, Stéphane Pérennès · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #Limits and Structures in Graph Theory #Pathwidth #Combinatorics #Mathematics #Planar graph #Outerplanar graph #Discrete mathematics #1-planar graph #Graph #Chordal graph #Line graph
paper · doi:10.1137/060670146
openalex publication_date 2009/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/02
We present a result concerning the relation between the path-width of a plane graph and the path-width of its dual. We prove that for a 3-connected planar graph G, \rm pw(G)≤3\rm pw(G^*)+2. For 4-connected planar graphs, and more generally for Hamiltonian planar graphs, we prove a stronger bound \rm pw(G^*)≤2~\rm pw(G)+c. The best previously known bound was obtained by Fomin and Thilikos who proved that \rm pw(G^*)≤6~\rm pw(G)+c. Our proof is based on a transformation which, given a fixed spanning tree of G, sends any given decomposition of G into one of G^*. The ratio of the corresponding parameters is bounded by the maximum degree of the spanning tree.