Special Issue on Selected Papers from the Seventh International Workshop on Algorithms and Computation, WALCOM 2013
Box-Rectangular Drawings of Planar Graphs
Md. Manzurul Hasan, Md. Saidur Rahman, and Md. Rezaul Karim
Vol. 17, no. 6, pp. 629-646, 2013. Regular paper.
Abstract A plane graph is a planar graph with a fixed planar embedding in the plane. In a box- rectangular drawing of a plane graph, every vertex is drawn as a rectangle, called a box, each edge is drawn as either a horizontal line segment or a vertical line segment, and the contour of each face is drawn as a rectangle. A planar graph is said to have a box-rectangular drawing if at least one of its plane embeddings has a box-rectangular drawing. Rahman et al.  gave a necessary and sufficient condition for a plane graph to have a box-rectangular drawing and developed a linear-time algorithm to draw a box-rectangular drawing of a plane graph if it exists. Since a planar graph G may have an exponential number of planar embeddings, determining whether G has a box-rectangular drawing or not using the algorithm of Rahman et al.   for each planar embedding of G takes exponential time. Thus to develop an efficient algorithm to examine whether a planar graph has a box-rectangular drawing or not is a non-trivial problem. In this paper we give a linear-time algorithm to determine whether a planar graph G has a box-rectangular drawing or not, and to find a box-rectangular drawing of G if it exists.
Submitted: April 2013.
Reviewed: September 2013.
Revised: October 2013.
Accepted: October 2013.
Final: October 2013.
Published: November 2013.
Communicated by Subir Kumar Ghosh
article (PDF)