On self duality of pathwidth in polyhedral graph embeddings
Fedor V. Fomin, Dimitrios M. Thilikos · Journal of Graph Theory · 2007
Abstract Let G be a 3‐connected planar graph and G * be its dual. We show that the pathwidth of G * is at most 6 times the pathwidth of G . We prove this result by relating the pathwidth of a graph with the cut‐width of its medial graph and we extend it to bounded genus embeddings. We also show that there exist 3‐connected planar graphs such that the pathwidth of such a graph is at least 1.5 times the pathwidth of its dual. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 42–54, 2007