2007/01/30 by Fedor V. Fomin, Dimitrios M. Thilikos · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #Graph Labeling and Dimension Problems #Pathwidth #Mathematics #Combinatorics #Outerplanar graph #Planar graph #Discrete mathematics #Bounded function #Graph #Dual graph #Line graph
paper · doi:10.1002/jgt.20219
openalex publication_date 2007/01/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11
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