Pathwidth of planar and line graphs (Q1396654)

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.