Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
|
DOI: 10.7155/jgaa.00233 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. Final: December 2010. Published: July 2011. Revised: July 2010. Reviewed: September 2009. Accepted: October 2010. Communicated by Sandip Das and Ryuhei Uehara |
| Journal of Graph Algorithms and Applications |