Orthogonal Drawings of Plane Graphs without Bends

Rahman, Md. Saidur and Naznin, Mahmuda and Nishizeki, Takao (2002) Orthogonal Drawings of Plane Graphs without Bends. In: Graph Drawing 9th International Symposium, GD 2001, September 23-26, 2001 , pp. 392-406(Official URL: http://dx.doi.org/10.1007/3-540-45848-4_31).

Full text not available from this repository.


In an orthogonal drawing of a plane graph G each vertex is drawn as a point and each edge is drawn as a sequence of vertical and horizontal line segments. A point at which the drawing of an edge changes its direction is called a bend. 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.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-45848-4_31
Classifications: G Algorithms and Complexity > G.999 Others
M Methods > M.600 Planar
G Algorithms and Complexity > G.210 Bends
P Styles > P.600 Poly-line > P.600.700 Orthogonal
URI: http://gdea.informatik.uni-koeln.de/id/eprint/519

Actions (login required)

View Item View Item