Approximation of pathwidth of outerplanar graphs

DOI10.1016/S0196-6774(02)00001-9zbMath1005.68113OpenAlexW2100609334WikidataQ59567890 ScholiaQ59567890MaRDI QIDQ3150282

Fedor V. Fomin, Hans L. Bodlaender

Publication date: 30 September 2002

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0196-6774(02)00001-9

zbMATH Keywords

outerplanar graphs

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10)

Related Items (16)

Linear-time algorithms for problems on planar graphs with fixed disk dimension ⋮ Computing the vertex separation of unicyclic graphs ⋮ Approximate search strategies for weighted trees ⋮ Approximating Pathwidth for Graphs of Small Treewidth ⋮ Splitting plane graphs to outerplanarity ⋮ Pathlength of outerplanar graphs ⋮ On self-duality of branchwidth in graphs of bounded genus ⋮ Branchwidth is \((1, g)\)-self-dual ⋮ Pathwidth of Circular-Arc Graphs ⋮ Pathwidth vs Cocircumference ⋮ Tree \(t\)-spanners in outerplanar graphs via supply demand partition ⋮ A 3-approximation for the pathwidth of Halin graphs ⋮ A 3-approximation for the pathwidth of Halin graphs ⋮ Non-deterministic graph searching in trees ⋮ Connected Graph Searching in Outerplanar Graphs ⋮ Circumference and Pathwidth of Highly Connected Graphs

This page was built for publication: Approximation of pathwidth of outerplanar graphs