On self duality of pathwidth in polyhedral graph embeddings

Fedor V. Fomin, Dimitrios M. Thilikos

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)42-54
Number of pages13
JournalJournal of Graph Theory
Issue number1
StatePublished - May 2007


  • Duality
  • Embeddings
  • Pathwidth

ASJC Scopus subject areas

  • Geometry and Topology


Dive into the research topics of 'On self duality of pathwidth in polyhedral graph embeddings'. Together they form a unique fingerprint.

Cite this