Home | Issues | About JGAA | Instructions for Authors |
Advances in Graph Drawing. Special Issue on Selected Papers from
the Ninth International Symposium on Graph Drawing, GD 2001
DOI: 10.7155/jgaa.00074
Orthogonal Drawings of Plane Graphs Without Bends
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.
|
Journal Supporters
|