On the Hardness of Orthogonal-Order Preserving Graph Drawing

Brandes, Ulrik and Pampel, Barbara (2009) On the Hardness of Orthogonal-Order Preserving Graph Drawing. In: Graph Drawing 16th International Symposium, GD 2008, September 21- 24, 2008 , pp. 266-277(Official URL: http://dx.doi.org/10.1007/978-3-642-00219-9_25).

Full text not available from this repository.


There are several scenarios in which a given drawing of a graph is to be modified subject to preservation constraints. Examples include shape simplification, sketch-based, and dynamic graph layout. While the orthogonal ordering of vertices is a natural and frequently called for preservation constraint, we show that, unfortunately, it results in severe algorithmic difficulties even for the simplest graphs. More precisely, we show that orthogonal-order preserving rectilinear and uniform edge length drawing is N P -hard even for paths.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-642-00219-9_25
Classifications: Z Theory > Z.250 Geometry
URI: http://gdea.informatik.uni-koeln.de/id/eprint/912

Actions (login required)

View Item View Item