On self duality of pathwidth in polyhedral graph embeddings

Fedor V. Fomin; Dimitrios M. Thilikos

doi:10.1002/jgt.20219

On self duality of pathwidth in polyhedral graph embeddings

Fedor V. Fomin, Dimitrios M. Thilikos

Computer Science

Research output: Contribution to journal › Article › peer-review

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.

Original language	English (US)
Pages (from-to)	42-54
Number of pages	13
Journal	Journal of Graph Theory
Volume	55
Issue number	1
DOIs	https://doi.org/10.1002/jgt.20219
State	Published - May 2007

Keywords

Duality
Embeddings
Pathwidth

ASJC Scopus subject areas

Geometry and Topology

Access to Document

10.1002/jgt.20219

Cite this

@article{b61b88c913e2435c9295e4786c4a5a83,

title = "On self duality of pathwidth in polyhedral graph embeddings",

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.",

keywords = "Duality, Embeddings, Pathwidth",

author = "Fomin, {Fedor V.} and Thilikos, {Dimitrios M.}",

year = "2007",

month = may,

doi = "10.1002/jgt.20219",

language = "English (US)",

volume = "55",

pages = "42--54",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "1",

}

TY - JOUR

T1 - On self duality of pathwidth in polyhedral graph embeddings

AU - Fomin, Fedor V.

AU - Thilikos, Dimitrios M.

PY - 2007/5

Y1 - 2007/5

N2 - 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.

AB - 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.

KW - Duality

KW - Embeddings

KW - Pathwidth

UR - http://www.scopus.com/inward/record.url?scp=34248203058&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=34248203058&partnerID=8YFLogxK

U2 - 10.1002/jgt.20219

DO - 10.1002/jgt.20219

M3 - Article

AN - SCOPUS:34248203058

SN - 0364-9024

VL - 55

SP - 42

EP - 54

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 1

ER -

On self duality of pathwidth in polyhedral graph embeddings

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this