2-connecting outerplanar graphs without blowing up the pathwidth

DOI10.1016/j.tcs.2014.04.032zbMath1383.68058OpenAlexW2095283118MaRDI QIDQ744095

Deepak Rajendraprasad, Jasine Babu, L. Sunil Chandran, Manu Basavaraju

Publication date: 6 October 2014

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.04.032

zbMATH Keywords

pathwidthouterplanar graph2-vertex-connected

Mathematics Subject Classification ID

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

Related Items (4)

A Polynomial-Time Algorithm for Outerplanar Diameter Improvement ⋮ A polynomial-time algorithm for outerplanar diameter improvement ⋮ B0-VPG Representation of AT-free Outerplanar Graphs ⋮ Triangulating Planar Graphs While Keeping the Pathwidth Small

Uses Software

• Algorithm 447

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximating the pathwidth of outerplanar graphs
• Small drawings of outerplanar graphs, series-parallel graphs, and other planar graphs
• Graph minors. III. Planar tree-width
• Augmenting the connectivity of outerplanar graphs
• Characterizations of outerplanar graphs
• Construction of linear tree-layouts which are optimal with respect to vertex separation in linear time
• PATHWIDTH AND LAYERED DRAWINGS OF TREES
• Augmenting Outerplanar Graphs

This page was built for publication: 2-connecting outerplanar graphs without blowing up the pathwidth