×

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

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C85 Graph algorithms (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: Link