×

zbMATH — the first resource for mathematics

Morphing Schnyder drawings of planar triangulations. (English) Zbl 1409.68202
It is a known fact that, given a triangulation on \(n\) vertices and two straight-line planar drawings of it, \(\Gamma\) and \(\Gamma^\prime\), that have the same unbounded face, it is possible to morph from \(\Gamma\) to \(\Gamma^\prime\) while preserving straight-line planarity. Various morphing algorithms are already known. In [SIAM J. Comput. 46, No. 2, 824–852 (2017; Zbl 1370.68224)] the authors give a morph that consists of \(O(n)\) linear morphs that moves each of the \(n\) vertices in a straight line at uniform speed. However, the resulting grid size of the intermediate drawings is not bounded and the morphs are not good for visualization purposes.
The algorithm of this paper uses Schnyder embeddings to morph in \(O(n^2)\) linear morphing steps while all \(O(n^2)\) intermediate drawings are on a \(6n\times 6n\) grid for a significant class of drawings of triangulations, namely the class of weighted Schnyder drawings. Furthermore, the morphs are visually attractive.
A Schnyder wood is a special type of partition (colouring) and orientation of the edges of a planar triangulation into three rooted directed trees. Weighted Schnyder drawings are obtained from a Schnyder wood together with an assignment of positive weights to the interior faces. The method in the paper involves implementing the basic “flip” operations of Schnyder woods as linear morphs.
MSC:
68R10 Graph theory (including graph drawing) in computer science
05C10 Planar graphs; geometric and topological aspects of graph theory
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
Software:
GVF
PDF BibTeX Cite
Full Text: DOI
References:
[1] Alamdari, S., Angelini, P., Chan, T.M., Di Battista, G., Frati, F., Lubiw, A., Patrignani, M., Roselli, V., Singla, S., Wilkinson, B.T.: Morphing planar graph drawings with a polynomial number of steps. In: Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’13), pp. 1656-1667. SIAM, Philadelphia (2013)
[2] Alamdari, S.; Angelini, P.; Barrera-Cruz, F.; Chan, TM; Lozzo, G.; Battista, G.; Frati, F.; Haxell, P.; Lubiw, A.; Patrignani, M.; Roselli, V.; Singla, S.; Wilkinson, BT, How to morph planar graph drawings, SIAM J. Comput., 46, 824-852, (2017) · Zbl 1370.68224
[3] Angelini, P., Da Lozzo, G., Di Battista, G., Frati, F., Patrignani, M., Roselli, V.: Morphing planar graph drawings optimally. In: Esparza, J., et al. (eds.) Proceedings of the 41st International Colloquium on Automata, Languages and Programming (ICALP’14). Lecture Notes in Computer Sciences, vol. 8572, pp. 126-137. Springer, Heidelberg (2014) · Zbl 1409.68200
[4] Angelini, P., Da Lozzo, G., Frati, F., Lubiw, A., Patrignani, M., Roselli, V.: Optimal morphs of convex drawings. In: Arge, L., Pach, J. (eds.) Proceedings of the 31st International Symposium on Computational Geometry (SoCG’15). Leibniz International Proceedings in Informatics, vol. 34, pp. 126-140. Schloss Dagstuhl. Leibniz-Zentrum für Informatik, Wadern (2015) · Zbl 1378.68149
[5] Archambault, D.; Purchase, H.; Pinaud, B., Animation, small multiples, and the effect of mental map preservation in dynamic graphs, IEEE Trans. Vis. Comput. Graph., 17, 539-552, (2011)
[6] Barrera-Cruz, F.: Morphing Planar Triangulations. Ph.D. thesis, University of Waterloo (2014) · Zbl 1427.68227
[7] Barrera-Cruz, F., Haxell, P., Lubiw, A.: Morphing planar graphs with unidirectional moves. In: Mexican Conference on Discrete Mathematics and Computational Geometry (2013) · Zbl 1427.68227
[8] Barrera-Cruz, F., Haxell, P., Lubiw, A.: Morphing Schnyder drawings of planar triangulations. In: Duncan, C., Symvonis, A. (eds.) Graph Drawing: 22nd International Symposium (GD’14). Lecture Notes in Computer Science, 8871, pp. 294-305. Springer, Heidelberg (2014) · Zbl 1427.68227
[9] Barrera-Cruz, F., Haxell, P., Lubiw, A.: Schnyder morphs. http://www.math.uwaterloo.ca/ fbarrera/morphing.html. Accessed 27 Feb 2017 · Zbl 1427.68227
[10] Bennett, C., Ryall, J., Spalteholz, L., Gooch, A.: The aesthetics of graph visualization. In: Proceedings of the 3rd Eurographics Conference on Computational Aesthetics in Graphics, Visualization and Imaging, pp. 57-64. Eurographics Association (2007)
[11] Bonichon, N., Gavoille, C., Hanusse, N., Ilcinkas, D.: Connections between theta-graphs, Delaunay triangulations, and orthogonal surfaces. In: Thilikos, D.M. (ed.) Graph-Theoretic Concepts in Computer Science: 36th International Workshop (WG’10). Lecture Notes in Computer Science, vol. 6410, pp. 266-278. Springer, Berlin (2010) · Zbl 1309.68146
[12] Brehm, E.: 3-Orientations and Schnyder 3-Tree-Decompositions. Master’s thesis, FB Mathematik und Informatik, Freie Universität Berlin. http://page.math.tu-berlin.de/ felsner/Diplomarbeiten/brehm.ps.gz (2000)
[13] Cairns, SS, Deformations of plane rectilinear complexes, Am. Math. Mon., 51, 247-252, (1944) · Zbl 0063.00684
[14] Dhandapani, R., Greedy drawings of triangulations, Discrete Comput. Geom., 43, 375-392, (2010) · Zbl 1213.05180
[15] Eppstein, D., Mumford, E., Speckmann, B., Verbeek, K.: Area-universal rectangular layouts. In: Proceedings of the 25th Annual Symposium on Computational Geometry (SoCG’09), pp. 267-276. ACM, New York (2009) · Zbl 1380.68394
[16] Felsner, S., Zickfeld, F.: On the number of \(\alpha \)-orientations. In: Brandstädt, A., et al. (eds.) Graph-Theoretic Concepts in Computer Science: 33rd International Workshop (WG’07). Lecture Notes in Computer Science, vol. 4769, pp. 190-201. Springer, Berlin (2007) · Zbl 1142.05017
[17] Felsner, S.: Lattice structures from planar graphs. Electron. J. Comb. 11(1). Art. No. 15 (2004) · Zbl 1056.05039
[18] Felsner, S., Convex drawings of planar graphs and the order dimension of 3-polytopes, Order, 18, 19-37, (2001) · Zbl 0984.05029
[19] Felsner, S., Geodesic embeddings and planar graphs, Order, 20, 135-150, (2003) · Zbl 1033.05028
[20] Felsner, S.; Zickfeld, F., Schnyder woods and orthogonal surfaces, Discrete Comput. Geom., 40, 103-126, (2008) · Zbl 1148.05026
[21] Floater, MS; Gotsman, C., How to morph tilings injectively, J. Comput. Appl. Math., 101, 117-129, (1999) · Zbl 0946.52010
[22] Herman, I.; Melançon, G.; Marshall, MS, Graph visualization and navigation in information visualization: A survey, IEEE Trans. Vis. Comput. Graph., 6, 24-43, (2000)
[23] Miracle, S., Randall, D., Streib, A.P., Tetali, P.: Algorithms for sampling 3-orientations of planar triangulations. CoRR arXiv:1202.4945 (2012) · Zbl 1296.05057
[24] Miracle, S.; Randall, D.; Streib, AP; Tetali, P., Sampling and counting 3-orientations of planar triangulations, SIAM J. Discrete Math., 30, 801-831, (2016) · Zbl 1337.60174
[25] Ossona de Mendez, P.: Orientations Bipolaires. Ph.D. thesis, L’École des Hautes Études en Sciences Sociales, Paris (1994)
[26] Schnyder, W.: Embedding planar graphs on the grid. In: Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’90), pp. 138-148. SIAM, Philadelphia (1990) · Zbl 0786.05029
[27] Schnyder, W., Planar graphs and poset dimension, Order, 5, 323-343, (1989) · Zbl 0675.06001
[28] Surazhsky, V.; Gotsman, C., Controllable morphing of compatible planar triangulations, ACM Trans. Graph., 20, 203-231, (2001) · Zbl 1151.68708
[29] Tutte, WT, How to draw a graph, Proc. Lond. Math. Soc., 13, 743-768, (1963) · Zbl 0115.40805
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.