Height-Preserving Transformations of Planar Graph Drawings

Biedl, Therese (2014) Height-Preserving Transformations of Planar Graph Drawings. In: Graph Drawing 22nd International Symposium, GD 2014, September 24-26, 2014, Würzburg, Germany , pp. 380-391 (Official URL: http://dx.doi.org/10.1007/978-3-662-45803-7_32).

Full text not available from this repository.


There are numerous styles of planar graph drawings, such as straight-line drawings, poly-line drawings, orthogonal graph drawings and visibility representations. Given a planar drawing in one of these styles, can it be converted it to another style while keeping the height unchanged? This paper answers this question for (nearly) all pairs of these styles, as well as for related styles that additionally restrict edges to be y-monotone and/or vertices to be horizontal line segments. These transformations can be used to develop new graph drawing results, especially for height-optimal drawings.

Item Type:Conference Paper
Additional Information:10.1007/978-3-662-45803-7_32
Classifications:G Algorithms and Complexity > G.070 Area / Edge Length
P Styles > P.540 Planar
P Styles > P.600 Poly-line
P Styles > P.600 Poly-line > P.600.700 Orthogonal
P Styles > P.720 Straight-line
P Styles > P.900 Visibility
ID Code:1448

Repository Staff Only: item control page


Babu, J., Basavaraju, M., Chandran Leela, S., Rajendraprasad, D. 2-connecting outerplanar graphs without blowing up the pathwidth. In: Du, D.-Z., Zhang, G. eds. (2013) Computing and Combinatorics. Springer, Heidelberg, pp. 626-637

Biedl, T. A 4-approximation for the height of drawing 2-connected outer-planar graphs. In: Erlebach, T., Persiano, G. eds. (2013) Approximation and Online Algorithms. Springer, Heidelberg, pp. 272-285

Biedl, T., Lubiw, A., Petrick, M., Spriggs, M.J. (2013) Morphing orthogonal planar graph drawings. ACM Transactions on Algorithms 9: pp. 29

Biedl, T., Bläsius, T., Niedermann, B., Nöllenburg, M., Prutkin, R., Rutter, I. Using ILP/SAT to Determine Pathwidth, Visibility Representations, and other Grid-Based Graph Drawings. In: Wismath, S., Wolff, A. eds. (2013) Graph Drawing. Springer, Heidelberg, pp. 460-471

Chimani, M., Zeranski, R. Upward planarity testing via SAT. In: Didimo, W., Patrignani, M. eds. (2013) Graph Drawing. Springer, Heidelberg, pp. 248-259

Dujmovic, V., Fellows, M., Kitching, M., Liotta, G., McCartin, C., Nishimura, N., Ragde, P., Rosamond, F., Whitesides, S., Wood, D. (2008) On the parameterized complexity of layered graph drawing. Algorithmica 52: pp. 267-292

Felsner, S., Liotta, G., Wismath, S. (2003) Straight-line drawings on restricted integer grids in two and three dimensions. Journal of Graph Algorithms and Applications 7: pp. 335-362

Fraysseix, H., Pach, J., Pollack, R. (1990) How to draw a planar graph on a grid. Combinatorica 10: pp. 41-51

Garg, A., Tamassia, R. (2001) On the computational complexity of upward and rectilinear planarity testing. SIAM J. Comput. 31: pp. 601-625

He, X., Wang, J., Zhang, H. (2012) Compact visibility representation of 4-connected plane graphs. Theor. Comput. Sci. 447: pp. 62-73

Hoffmann, M., van Kreveld, M., Kusters, V., Rote, G.: Quality ratios of measures for graph drawing styles. In: Canadian Conference on Computational Geometry, CCCG 2014 (to appear, 2014)

Kant, G. (1996) Drawing planar graphs using the canonical ordering. Algorithmica 16: pp. 4-32

Lengauer, T.: Combinatorial Algorithms for Integrated Circuit Layout. Teubner/Wiley & Sons, Stuttgart/Chicester (1990)

Miura, K., Nakano, S., Nishizeki, T. (2006) Convex grid drawings of four-connected plane graphs. Int. J. Found. Comput. Sci. 17: pp. 1031-1060

Pach, J., Tóth, G. (2004) Monotone drawings of planar graphs. Journal of Graph Theory 46: pp. 39-47

Rosenstiehl, P., Tarjan, R.E. (1986) Rectilinear planar layouts and bipolar orientation of planar graphs. Discrete Computational Geometry 1: pp. 343-353

Schnyder, W.: Embedding planar graphs on the grid. In: ACM-SIAM Symposium on Discrete Algorithms (SODA 1990), pp. 138–148 (1990)

Biedl, T., Kant, G. (1998) A better heuristic for orthogonal graph drawings. Computational Geometry: Theory and Applications 9: pp. 159-180

Biedl, T., Kaufmann, M., Mutzel, P. Drawing planar partitions II: HH-drawings. In: Hromkovič, J., Sýkora, O. eds. (1998) Graph-Theoretic Concepts in Computer Science. Springer, Heidelberg, pp. 124-136

Tamassia, R., Tollis, I. (1986) A unified approach to visibility representations of planar graphs. Discrete Computational Geometry 1: pp. 321-341

Wismath, S.: Characterizing bar line-of-sight graphs. In: ACM Symposium on Computational Geometry (SoCG 1985), pp. 147–152 (1985)