Home | Issues | About JGAA | Instructions for Authors |
Special Issue on Selected Papers from the Third Annual Workshop on Algorithms and Computation (WALCOM 2009)
DOI: 10.7155/jgaa.00233
Straight-Line Grid Drawings of Label-Constrained Outerplanar Graphs with O(n log n) Area
Vol. 15, no. 3, pp. 437-456, 2011. Regular paper.
Abstract A straight-line grid drawing of a planar graph G is a drawing of G on an integer grid such that each vertex is drawn as a grid
point and each edge is drawn as a straight-line segment without edge crossings. Any outerplanar graph of n vertices with maximum degree d has a straight-line grid
drawing with area O(dnlogn).
In this paper, we introduce a subclass of outerplanar graphs, which we call label-constrained outerplanar graphs, that admits
straight-line grid drawings with O(nlogn) area.
We give a linear-time algorithm to find such a drawing. We also give a linear-time algorithm for the recognition of label-constrained
outerplanar graphs.
|
Submitted: May 2009.
Reviewed: September 2009.
Revised: July 2010.
Accepted: October 2010.
Final: December 2010.
Published: July 2011.
|
Journal Supporters
|