Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
|
DOI: 10.7155/jgaa.00074 Orthogonal Drawings of Plane Graphs Without Bends Md. Saidur Rahman , Takao Nishizeki , and Mahmuda Naznin Vol. 7, no. 4, pp. 335-362, 2003. Regular paper Abstract In an orthogonal drawing of a plane graph each vertex is drawn as a point and each edge is drawn as a sequence of vertical and horizontal line segments. A bend is a point at which the drawing of an edge changes its direction. Every plane graph of the maximum degree at most four has an orthogonal drawing, but may need bends. A simple necessary and sufficient condition has not been known for a plane graph to have an orthogonal drawing without bends. In this paper we obtain a necessary and sufficient condition for a plane graph G of the maximum degree three to have an orthogonal drawing without bends. We also give a linear-time algorithm to find such a drawing of G if it exists.
|
Submitted: May 2002. Revised: November 2002. Communicated by Petra Mutzel and Michael Jünger |
| Journal of Graph Algorithms and Applications |