Pathwidth of planar and line graphs
The paper studies the pathwidth \(\text{pw}(G)\) of planar graphs and proves that for any 2-connected plane graph \(G\) with pathwidth \(\text{pw}(G^*)\) of the geometric dual graph \(G^*\) of \(G\) is smaller than the pathwidth \(\text{pw}(L(G))\) of the line graph \(L(G)\) of \(G\). The technique of proof is appropriate also for the corresponding result \(\text{tw}(G^*)\leq \text{tw}(L(G))\) on treewidths. Further it is shown that \(\text{pw}(G)\geq \text{pw}(G^*)- 1\) for every 2-connected planar graph \(G\) of maximum degree at most 3 and the author conjectures that this might hold without the restriction on the degree.
- 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)
