Pathlength of outerplanar graphs

DOI10.1016/J.TCS.2026.115759MaRDI QIDQ6858868zbMATH OpenFDO

Authors Thomas Dissaux, Nicolas Nisse

Publication date 12 February 2026

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2026.115759

zbMATH Keywords

outerplanar graphpath-decompositionpathlength

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Cites work

• \(k\)-chordal graphs: from cops and robber to compact routing via treewidth
• A partial k-arboretum of graphs with bounded treewidth
• Approximation of pathwidth of outerplanar graphs
• Bounded-diameter tree-decompositions
• Dividing a Graph into Triconnected Components
• Dynamic analysis of the arrow distributed protocol
• Graphs on surfaces
• Line-distortion, bandwidth and path-length of a graph
• Linear algorithms to recognize outerplanar and maximal outerplanar graphs
• Metric Dimension of Bounded Tree-length Graphs
• Min Cut is NP-complete for edge weighted trees
• Minimum eccentricity shortest paths in some structured graph classes
• Monadic second-order definable graph orderings
• On the complexity of computing treebreadth
• On the complexity of computing treelength
• Pathlength of outerplanar graphs
• Pathwidth of outerplanar graphs
• To approximate treewidth, use treelength!
• Tree-decompositions with bags of small diameter
• Treelength of series-parallel graphs

This page was built for publication: Pathlength of outerplanar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6858868)