Home  Issues  About JGAA  Instructions for Authors 
Special Issue on Selected Papers from the Seventh International Workshop on Algorithms and Computation, WALCOM 2013
DOI: 10.7155/jgaa.00309
BoxRectangular Drawings of Planar Graphs
Md. Manzurul Hasan,
Md. Saidur Rahman, and
Md. Rezaul Karim
Vol. 17, no. 6, pp. 629646, 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 boxrectangular drawing if at least one of its plane embeddings has a boxrectangular drawing. Rahman et al. gave a necessary and sufficient condition for a plane graph to have a boxrectangular drawing and developed a lineartime algorithm to draw a boxrectangular 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 boxrectangular 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 boxrectangular drawing or not is a nontrivial problem. In this paper we give a lineartime algorithm to determine whether a planar graph G has a boxrectangular drawing or not, and to find a boxrectangular 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

Journal Supporters
