A Pairing Technique for Area-Efficient Orthogonal Drawings

Papakostas, Achilleas and Tollis, Ioannis G. (1997) A Pairing Technique for Area-Efficient Orthogonal Drawings. In: Symposium on Graph Drawing, GD '96, September 18-20, 1996 , pp. 355-370(Official URL: http://dx.doi.org/10.1007/3-540-62495-3_60).

Full text not available from this repository.


An orthogonal drawing of a graph is a drawing such that vertices are placed on grid points and edges are drawn as sequences of vertical and horizontal segments. In this paper we present linear time algorithms that produce orthogonal drawings of graphs with n nodes. If the maximum degree is four, then the drawing produced by our first algorithm needs area not greater than 0.76n², and introduces no more than 2n+2 bends. Also, every edge of such a drawing has at most two bends. Our algorithm is based on forming and placing pairs of vertices of the graph. If the maximum degree is three, then the drawing produced by our second algorithm needs at most 0.25n² area, and at most \lfloor 0.5n+2l+1 \rfloor bends (\lfloor 0.5n \rfloor +3 bends, if the graph isbiconnected), where l is the number of biconnected components that are leaves in th block tree. For biconnected graphs, this algorithm produces optimal drawings with respect to the number of bends (within a constant of two), since there is a lower bound of 0.5n+1 in the number of bends for orthogonal drawings of degree 3 graphs.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-62495-3_60
Classifications: G Algorithms and Complexity > G.070 Area / Edge Length
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/109

Actions (login required)

View Item View Item