Abstract
A rectangular dual of a plane graph G is a contact representations of G by interior-disjoint axis-aligned rectangles such that (i) no four rectangles share a point and (ii) the union of all rectangles is a rectangle. A rectangular dual gives rise to a regular edge labeling (REL), which captures the orientations of the rectangle contacts.
We study the problem of morphing between two rectangular duals of the same plane graph. If we require that, at any time throughout the morph, there is a rectangular dual, then a morph exists only if the two rectangular duals realize the same REL. Therefore, we allow intermediate contact representations of non-rectangular polygons of constant complexity. Given an n-vertex plane graph, we show how to compute in \(\mathcal {O}(n^3)\) time a piecewise linear morph that consists of \(\mathcal {O}(n^2)\) linear morphing steps.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Alamdari, S., et al.: How to morph planar graph drawings. SIAM J. Comput. 46(2), 824–852 (2017). https://doi.org/10.1137/16M1069171
Angelini, P., Chaplick, S., Cornelsen, S., Da Lozzo, G., Roselli, V.: Morphing contact representations of graphs. In: Barequet, G., Wang, Y. (eds.) Symp. Comput. Geom. (SoCG). LIPIcs, vol. 129, pp. 10:1–10:16. Schloss Dagstuhl - LZI (2019). https://doi.org/10.4230/LIPIcs.SoCG.2019.10
Angelini, P., Da Lozzo, G., Frati, F., Lubiw, A., Patrignani, M., Roselli, V.: Optimal morphs of convex drawings. In: Arge, L., Pach, J. (eds.) Symp. Comput. Geom. (SoCG). LIPIcs, vol. 34, pp. 126–140. Schloss Dagstuhl - LZI (2015). https://doi.org/10.4230/LIPIcs.SOCG.2015.126
Arseneva, E., et al.: Pole dancing: 3D morphs for tree drawings. J. Graph Alg. Appl. 23(3), 579–602 (2019). https://doi.org/10.7155/jgaa.00503
Barrera-Cruz, F., Haxell, P., Lubiw, A.: Morphing schnyder drawings of Planar Triangulations. Discrete CMS. Geom. 61(1), 161–184 (2018). https://doi.org/10.1007/s00454-018-0018-9
Biedl, T., Lubiw, A., Petrick, M., Spriggs, M.: Morphing orthogonal planar graph drawings. ACM Trans. Algorithms 9(4) (2013). https://doi.org/10.1145/2500118
Booth, K.S., Lueker, G.S.: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. Syst. Sci. 13(3), 335–379 (1976). https://doi.org/10.1016/S0022-0000(76)80045-1
Buchin, K., Speckmann, B., Verdonschot, S.: Evolution strategies for optimizing rectangular cartograms. In: Xiao, N., Kwan, M.-P., Goodchild, M.F., Shekhar, S. (eds.) GIScience 2012. LNCS, vol. 7478, pp. 29–42. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-33024-7_3
Cairns, S.S.: Deformations of plane rectilinear complexes. Amer. Math. Monthly 51(5), 247–252 (1944). https://doi.org/10.1080/00029890.1944.11999082
Chambers, E.W., Erickson, J., Lin, P., Parsa, S.: How to morph graphs on the torus. In: Marx, D. (ed.) Symp. Discrete Algorithms (SODA), pp. 2759–2778 (2021). https://doi.org/10.1137/1.9781611976465.164
Chaplick, S., Kindermann, P., Klawitter, J., Rutter, I., Wolff, A.: Morphing rectangular duals (2022). https://doi.org/10.48550/ARXIV.2112.03040
Felsner, S.: Rectangle and square representations of planar graphs. In: Pach, J. (ed.) Thirty Essays on Geometric Graph Theory, pp. 213–248. Springer, New York (2013). https://doi.org/10.1007/978-1-4614-0110-0_12
Florisson, S., van Kreveld, M.J., Speckmann, B.: Rectangular cartograms: construction & animation. In: Mitchell, J.S.B., Rote, G. (eds.) ACM Symp. Comput. Geom. (SoCG), pp. 372–373 (2005). https://doi.org/10.1145/1064092.1064152
de Fraysseix, H., de Mendez, P.O., Rosenstiehl, P.: On triangle contact graphs. Combin. Prob. Comput. 3(2), 233–246 (1994). https://doi.org/10.1017/S0963548300001139
Fusy, É.: Transversal structures on triangulations, with application to straight-line drawing. In: Healy, P., Nikolov, N.S. (eds.) GD 2005. LNCS, vol. 3843, pp. 177–188. Springer, Heidelberg (2006). https://doi.org/10.1007/11618058_17
Fusy, É.: Transversal structures on triangulations: a combinatorial study and straight-line drawings. Discrete Math. 309(7), 1870–1894 (2009). https://doi.org/10.1016/j.disc.2007.12.093
Gabriel, K.R., Sokal, R.R.: A new statistical approach to geographic variation analysis. Syst. Biol. 18(3), 259–278 (1969). https://doi.org/10.2307/2412323
van Goethem, A., Speckmann, B., Verbeek, K.: Optimal morphs of planar orthogonal drawings II. In: Archambault, D., Tóth, C.D. (eds.) GD 2019. LNCS, vol. 11904, pp. 33–45. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-35802-0_3
He, X.: On finding the rectangular duals of planar triangular graphs. SIAM J. Comput. 22(6), 1218–1226 (1993). https://doi.org/10.1137/0222072
Heilmann, R., Keim, D.A., Panse, C., Sips, M.: Recmap: rectangular map approximations. In: Ward, M.O., Munzner, T. (eds.) IEEE Symp. Inform. Vis. (InfoVis), pp. 33–40 (2004). https://doi.org/10.1109/INFVIS.2004.57
Hoffmann, M., van Kreveld, M.J., Kusters, V., Rote, G.: Quality ratios of measures for graph drawing styles. In: Canadian Conf. Comput. Geom. (CCCG) (2014). http://www.cccg.ca/proceedings/2014/papers/paper05.pdf
Kant, G., He, X.: Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems. Theoret. Comput. Sci. 172(1), 175–193 (1997). https://doi.org/10.1016/S0304-3975(95)00257-X
Kobourov, S.G., Landis, M.: Morphing planar graphs in spherical space. J. Graph Alg. Appl. 12(1), 113–127 (2008). https://doi.org/10.7155/jgaa.00162
Koebe, P.: Kontaktprobleme der konformen Abbildung. Berichte über die Verhandlungen der Sächsischen Akademie der Wiss. zu Leipzig. Math.-Phys. Klasse 88, pp. 141–164 (1936)
Koźmiński, K., Kinnen, E.: Rectangular duals of planar graphs. Netw. 15(2), 145–157 (1985). https://doi.org/10.1002/net.3230150202
Leinwand, S.M., Lai, Y.: An algorithm for building rectangular floor-plans. In: 21st Design Automation Conference, pp. 663–664 (1984). https://doi.org/10.1109/DAC.1984.1585874
Nusrat, S., Kobourov, S.G.: The state of the art in cartograms. Comput. Graph. Forum 35(3), 619–642 (2016). https://doi.org/10.1111/cgf.12932
Purchase, Helen C.., Hoggan, Eve, Görg, Carsten: How Important is the mental map an empirical investigation of a dynamic graph layout algorithm. In: Kaufmann, Michael, Wagner, Dorothea (eds.) GD 2006. LNCS, vol. 4372. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-70904-6_19
Raisz, E.: The rectangular statistical cartogram. Geogr. Review 24(2), 292–296 (1934). https://doi.org/10.2307/208794. http://www.jstor.org/stable/208794
Steadman, P.: Graph theoretic representation of architectural arrangement. Archit. Res. Teach. 2(3) 161–172 (1973)
van Kreveld, M.J., Speckmann, B.: On rectangular cartograms. Comput. Geom. Theory Appl. 37(3), 175–187 (2007). https://doi.org/10.1016/j.comgeo.2006.06.002
Yeap, G.K.H., Sarrafzadeh, M.: Sliceable floorplanning by graph dualization. SIAM J. Discrete Math. 8(2), 258–280 (1995). https://doi.org/10.1137/S0895480191266700
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Chaplick, S., Kindermann, P., Klawitter, J., Rutter, I., Wolff, A. (2023). Morphing Rectangular Duals. In: Angelini, P., von Hanxleden, R. (eds) Graph Drawing and Network Visualization. GD 2022. Lecture Notes in Computer Science, vol 13764. Springer, Cham. https://doi.org/10.1007/978-3-031-22203-0_28
Download citation
DOI: https://doi.org/10.1007/978-3-031-22203-0_28
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-22202-3
Online ISBN: 978-3-031-22203-0
eBook Packages: Computer ScienceComputer Science (R0)