Special Issue on Selected Papers from the Third Annual Workshop on Algorithms and Computation (WALCOM 2009)
Straight-Line Grid Drawings of Label-Constrained Outerplanar Graphs with O(n log n) Area
Md. Rezaul Karim, Md. Jawaherul Alam, and Md. Saidur Rahman
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.
Communicated by Sandip Das and Ryuhei Uehara
article (PDF)