Improved Algorithms and Bounds for Orthogonal Drawings

Papakostas, Achilleas and Tollis, Ioannis G. (1995) Improved Algorithms and Bounds for Orthogonal Drawings. In: Graph Drawing DIMACS International Workshop, GD 1994, October 10–12, 1994 , pp. 40-51(Official URL: http://dx.doi.org/10.1007/3-540-58950-3_355).

Full text not available from this repository.

Abstract

An orthogonal drawing of a graph is a drawing such that nodes 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 algorithm needs area no greater than 0.8n^2 and no more than 1.9n bends. Notice that our upper bound on the bends is below the lower bound for planar orthogonal drawings of planar graphs. To the best of our knowledge, this is the first algorithm for orthogonal drawings that needs area less than n^2. If the maximum degree is three, then the drawing produced by our algorithm needs (\frac{n}{2}+1) \times \frac{n}{2} area and at most \frac{n}{2}+3 bends. These upper bounds match the upper bounds known for triconnected planar graphs of degree 3.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-58950-3_355
Classifications: G Algorithms and Complexity > G.070 Area / Edge Length
M Methods > M.600 Planar
G Algorithms and Complexity > G.210 Bends
P Styles > P.600 Poly-line > P.600.700 Orthogonal
P Styles > P.540 Planar
URI: http://gdea.informatik.uni-koeln.de/id/eprint/96

Actions (login required)

View Item View Item