Fomin, Fedor V.; Bodlaender, Hans L. Approximation of pathwidth of outerplanar graphs. (English) Zbl 1042.68630 Brandstädt, Andreas (ed.) et al., Graph-theoretic concepts in computer science. 27th international workshop, WG 2001, Boltenhagen, Germany, June 14–16, 2001. Proceedings. Berlin: Springer (ISBN 3-540-42707-4). Lect. Notes Comput. Sci. 2204, 166-176 (2001). Summary: There exists a polynomial time algorithm to compute the pathwidth of outerplanar graphs, but the large exponent makes this algorithm impractical. In this paper, we give an algorithm, that given a biconnected outerplanar graph \(G\), finds a path decomposition of \(G\) of pathwidth at most twice the pathwidth of \(G\) plus one. To obtain the result, several relations between the pathwidth of a biconnected outerplanar graph and its dual are established.For the entire collection see [Zbl 0983.00052]. Cited in 1 Document MSC: 68R10 Graph theory (including graph drawing) in computer science 05C85 Graph algorithms (graph-theoretic aspects) PDFBibTeX XMLCite \textit{F. V. Fomin} and \textit{H. L. Bodlaender}, Lect. Notes Comput. Sci. 2204, 166--176 (2001; Zbl 1042.68630) Full Text: Link