A Simple Linear Time Algorithm for Proper Box Rectangular Drawings of Plane Graphs

In this paper we introduce a new style of drawing a plane graph G, called proper box rectangular (PBR) drawing. It is defined to be a drawing of G such that every vertex is drawn as a rectangle, called a box, each edge is drawn as either a horizontal or a vertical line segment, and each face is drawn as a rectangle. We establish necessary and sufficient conditions for G to have a PBR drawing. We also give a simple linear time algorithm for finding such drawings. The PBR drawing is closely related to the box rectangular (BR) drawing defined by M. S. Rahman, S. Nakano and T. Nishizeki (2000, J. Algorithms 37, 363-398). Our method can be adapted to provide a new algorithm for solving the BR drawing problem.