## Improved Algorithms and Bounds for Orthogonal Drawings
Papakostas, Achilleas and Tollis, Ioannis G.
(1995)
Full text not available from this repository. ## AbstractAn 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.
Repository Staff Only: item control page References |