Premium
On self duality of pathwidth in polyhedral graph embeddings
Author(s) -
Fomin Fedor V.,
Thilikos Dimitrios M.
Publication year - 2007
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20219
Subject(s) - pathwidth , mathematics , combinatorics , outerplanar graph , planar graph , discrete mathematics , bounded function , graph , dual graph , line graph , mathematical analysis
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