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, Heraklion, Crete, Greece , 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 modiﬁed subject to preservation constraints. Examples include shape simpliﬁcation, 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 diﬃculties 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.
Repository Staff Only: item control page