Pathwidth of planar and line graphs

DOI10.1007/S00373-002-0490-ZMaRDI QIDQ1396654zbMATH OpenOpenAlexWikidataFDO

Authors Fedor V. Fomin

Publication date 8 July 2003

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00373-002-0490-z

zbMATH Keywords

cutwidthdual graphline graphspathwidthplanar graphssearch numbertreewidth

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• On the path-width of planar graphs
• Pathwidth of outerplanar graphs
• On self duality of pathwidth in polyhedral graph embeddings
• Triangulating planar graphs while keeping the pathwidth small
• Tree-width of hypergraphs and surface duality

Cited in

(12)

• Chordal embeddings of planar graphs
• Triangulating planar graphs while keeping the pathwidth small
• Tree-width of graphs and surface duality
• On the plane-width of graphs
• Path-width of a graph vs bridge number of a knot
• The plane-width of graphs
• Pathwidth of outerplanar graphs
• On self duality of pathwidth in polyhedral graph embeddings
• Paths of low weight in planar graphs
• On the path-width of planar graphs
• Tree-width of hypergraphs and surface duality
• The treewidth of line graphs

This page was built for publication: Pathwidth of planar and line graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1396654)