# 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 10.1007/3-540-58950-3_355 G Algorithms and Complexity > G.070 Area / Edge LengthM Methods > M.600 PlanarG Algorithms and Complexity > G.210 BendsP Styles > P.600 Poly-line > P.600.700 OrthogonalP Styles > P.540 Planar http://gdea.informatik.uni-koeln.de/id/eprint/96

### Actions (login required)

 View Item