Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
2-connecting Outerplanar Graphs without Blowing Up the Pathwidth
verfasst von : Jasine Babu, Manu Basavaraju, Sunil Chandran Leela, Deepak Rajendraprasad
Erschienen in: Computing and Combinatorics
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Given a connected outerplanar graph
G
with pathwidth
p
, we give an algorithm to add edges to
G
to get a supergraph of
G
, which is 2-vertex-connected, outerplanar and of pathwidth
O
(
p
). As a consequence, we get a constant factor approximation algorithm to compute a straight line planar drawing of any outerplanar graph, with its vertices placed on a two dimensional grid of minimum height. This settles an open problem raised by Biedl [3].