Improved Algorithms and Bounds for Orthogonal DrawingsPapakostas, 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. 4051(Official URL: http://dx.doi.org/10.1007/3540589503_355). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/3540589503_355
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.
Actions (login required)
