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.

Abstract

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
ID Code:912

Repository Staff Only: item control page

References

Agarwal, P., Har-Peled, S. , Mustafa, N. , Wang, Y.: Near-linear time approximation algorithms for path simplification. Algorithmica 42, 203–219 (2000)

Bachmaier, C., Brandes, U., Schlieper, B.: Drawing phylogenetic trees. In: ISAAC ’05. LNCS, vol. 3827, pp. 1110–1121. Springer, Heidelberg (2005)

Boehringer, K.-F., Newbery Paulisch, F.: Using constraints to achieve stability in automatic graph algorithms. In: Proc. of the ACM SIGCHI Conference on Human Factors in Computer Systems. pp. 43–51, 1990. WA (1990)

Bridgeman, S., Tamassia, R.: A user study in similarity measures for graph drawing. JGAA 6(3), 225–254 (2002)

Bridgeman, S., Tamassia, R.: Difference metrics for interactive orthogonal graph drawing algorithms. In: GD 98. LNCS, vol. 1547, pp. 57–71. Springer, Heidelberg (1999)

Carlson, J., Eppstein, D.: Trees with convex faces and optimal angles. In: GD 06. LNCS, vol. 4372, pp. 77–88. Springer, Heidelberg (2007)

Dwyer, T., Koren, Y., Marriott, K.: Stress majorization with orthogonal order constraints. In: GD 05. LNCS, vol. 3843, pp. 141–152. Springer, Heidelberg (2006)

Douglas, D., Peucker, T.: Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. Canad. Cartog. 10(2), 112–122 (1973)

Eades, R., Lai, W., Misue, K., Sugiyama, K.: Layout adjustment and the mental map. J. Visual Lang. Comput. 6, 183–210 (1995)

Eades, P., Wormald, N.: Fixed edge-length graph drawing is N P -hard. Discrete Appl. Math., 28, 111–134 (1990)

Garey, M., Johnson, D.: In: Computers and Intractability. W. H. Freeman and Company, New York (1979)

Imai, H., Iri, M.: An optimal algorithm for approximating a piecewise linear function.J. Inform. Process. 9(3), 159–162 (1986)

Lee, Y.-Y., Lin, C.-C., Yen, H.-C.: Mental map preserving graph drawing using simulated annealing. In: Proc. of the 2006 Asia-Pacific Symposium on Inforamtion Visualisation. pp 179–188. Australian Computer Science (2006)

Merrick, D., Gudmundsson, J.: Path simplification for metro map layout. In: GD 06. LNCS, vol. 4372, pp. 258–269. Springer, Heidelberg (2007)

Neyer, G.: Line simplification with restricted orientations. In: WADS 99. LNCS, vol. 1663, pp. 13–24. Springer, Heidelberg (1999)

Nöllenburg, M., Wolff, A.: A mixed-integer program for drawing high-quality o metro maps. In: GD 05. LNCS, vol. 3843, pp. 321–333. Springer, Heidelberg (2006)