On the Path-Width of Planar Graphs
Omid Amini, Florian Huc, Stéphane Pérennès · SIAM Journal on Discrete Mathematics · 2009
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)\leq3{\rm pw}(G^*)+2$. For 4-connected planar graphs, and more generally for Hamiltonian planar graphs, we prove a stronger bound ${\rm pw}(G^*)\leq2~{\rm pw}(G)+c$. The best previously known bound was obtained by Fomin and Thilikos who proved that ${\rm pw}(G^*)\leq6~{\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.