Header menu link for other important links
X
2-connecting outerplanar graphs without blowing up the pathwidth
, M. Basavaraju, S. Chandran Leela,
Published in
2013
Volume: 7936 LNCS
   
Pages: 626 - 637
Abstract
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]. © 2013 Springer-Verlag Berlin Heidelberg.
About the journal
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN03029743