Abstract
The operation of transforming one spanning tree into another by replacing an edge has been considered widely, both for general and geometric graphs. For the latter, several variants have been studied (e.g., edge slides and edge rotations). In a transition graph on the set \(\mathcal {T}(S)\) of noncrossing straight-line spanning trees on a finite point set S in the plane, two spanning trees are connected by an edge if one can be transformed into the other by such an operation. We study bounds on the diameter of these graphs, and consider the various operations both on general point sets and sets in convex position. In addition, we address the problem variant where operations may be performed simultaneously. We prove new lower and upper bounds for the diameters of the corresponding transition graphs and pose open problems.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Aichholzer, O., Asinowski, A., Miltzow, T.: Disjoint compatibility graph of non-crossing matchings of points in convex position. Electron. J. Comb. 22, P1 (2015)
Aichholzer, O., Aurenhammer, F., Huemer, C., Krasser, H.: Transforming spanning trees and pseudo-triangulations. Inf. Process. Lett. 97(1), 19–22 (2006)
Aichholzer, O., Aurenhammer, F., Hurtado, F.: Sequences of spanning trees and a fixed tree theorem. Comput. Geom. 21(1–2), 3–20 (2002)
Aichholzer, O., Reinhardt, K.: A quadratic distance bound on sliding between crossing-free spanning trees. Comput. Geom. 37(3), 155–161 (2007)
Akl, S.G., Islam, M.K., Meijer, H.: On planar path transformation. Inf. Process. Lett. 104(2), 59–64 (2007)
Aloupis, G., Barba, L., Langerman, S., Souvaine, D.L.: Bichromatic compatible matchings. Comput. Geom. 48(8), 622–633 (2015)
Avis, D., Fukuda, K.: Reverse search for enumeration. Discret. Appl. Math. 65(1–3), 21–46 (1996)
Bose, P., Czyzowicz, J., Gao, Z., Morin, P., Wood, D.R.: Simultaneous diagonal flips in plane triangulations. J. Graph Theory 54(4), 307–330 (2007)
Bose, P., Hurtado, F.: Flips in planar graphs. Comput. Geom. 42(1), 60–80 (2009)
Bose, P., Lubiw, A., Pathak, V., Verdonschot, S.: Flipping edge-labelled triangulations. Comput. Geom. (2017, in Press)
Buchin, K., Razen, A., Uno, T., Wagner, U.: Transforming spanning trees: a lower bound. Comput. Geom. 42(8), 724–730 (2009)
Cano, J., Díaz-Báñez, J.M., Huemer, C., Urrutia, J.: The edge rotation graph. Graphs Comb. 29(5), 1–13 (2013)
Cayley, A.: A theorem on trees. Q. J. Math. 23, 376–378 (1889)
Chang, J.M., Wu, R.Y.: On the diameter of geometric path graphs of points in convex position. Inf. Process. Lett. 109(8), 409–413 (2009)
Faudree, R., Schelp, R., Lesniak, L., Gyárfás, A., Lehel, J.: On the rotation distance of graphs. Discret. Math. 126(1), 121–135 (1994)
Chartrand, G., Saba, F., Zou, H.B.: Edge rotations and distance between graphs. Cas. Pest. Math. 110, 87–91 (1985)
Galtier, J., Hurtado, F., Noy, M., Pérennes, S., Urrutia, J.: Simultaneous edge flipping in triangulations. Int. J. Comput. Geom. Appl. 13(2), 113–134 (2003)
Goddard, W., Swart, H.C.: Distances between graphs under edge operations. Discret. Math. 161(1), 121–132 (1996)
Hernando, M., Hurtado, F., Márquez, A., Mora, M., Noy, M.: Geometric tree graphs of points in convex position. Discret. Appl. Math. 93(1), 51–66 (1999)
Hoffmann, M., Sharir, M., Sheffer, A., Tóth, C.D., Welzl, E.: Counting plane graphs: flippability and its applications. In: Dehne, F., Iacono, J., Sack, J.-R. (eds.) WADS 2011. LNCS, vol. 6844, pp. 524–535. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-22300-6_44
Huemer, C., de Mier, A.: Lower bounds on the maximum number of non-crossing acyclic graphs. Europ. J. Comb. 48, 48–62 (2015)
Ishaque, M., Souvaine, D.L., Tóth, C.D.: Disjoint compatible geometric matchings. Discret. Comput. Geom. 49, 89–131 (2013)
Kanj, I.A., Sedgwick, E., Xia, G.: Computing the flip distance between triangulations. Discret. Comput. Geom. 58(2), 313–344 (2017)
Keller, C., Perles, M.A.: Reconstruction of the geometric structure of a set of points in the plane from its geometric tree graph. Discret. Comput. Geom. 55(3), 610–637 (2016)
Lubiw, A., Masárová, Z., Wagner, U.: A proof of the orbit conjecture for flipping edge-labelled triangulations. In: Proceedings of the 33rd Symposium on Computational Geometry (SoCG 2017). LIPIcs, vol. 77, pp. 49:1–49:15. Schloss Dagstuhl (2017)
Lubiw, A., Pathak, V.: Flip distance between two triangulations of a point set is NP-complete. Comput. Geom. 49, 17–23 (2015)
Oxley, J.G.: Matroid Theory. Oxford University Press, Oxford (1993)
Pilz, A.: Flip distance between triangulations of a planar point set is APX-hard. Comput. Geom. 47(5), 589–604 (2014)
Pournin, L.: A combinatorial method to find sharp lower bounds on flip distances. In: Proceedings of the 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), pp. 1–12 (2013)
Sleator, D.D., Tarjan, R.E., Thurston, W.P.: Rotation distance, triangulations, and hyperbolic geometry. J. Am. Math. Soc. 1, 647–681 (1988)
Wu, R.Y., Chang, J.M., Pai, K.J., Wang, Y.L.: Amortized efficiency of generating planar paths in convex position. Theor. Comput. Sci. 412(35), 4504–4512 (2011)
Acknowledgment
Key ideas for our results on simultaneous edge slides were discussed at the GWOP 2017 workshop in Pochtenalp, Switzerland. We thank all participants for the constructive atmosphere. Research by Nichols and Tóth was partially supported by the NSF awards CCF-1422311 and CCF-1423615. Pilz is supported by a Schrödinger fellowship of the Austrian Science Fund (FWF): J-3847-N35.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG, part of Springer Nature
About this paper
Cite this paper
Nichols, T.L., Pilz, A., Tóth, C.D., Zehmakan, A.N. (2018). Transition Operations over Plane Trees. In: Bender, M., Farach-Colton, M., Mosteiro, M. (eds) LATIN 2018: Theoretical Informatics. LATIN 2018. Lecture Notes in Computer Science(), vol 10807. Springer, Cham. https://doi.org/10.1007/978-3-319-77404-6_60
Download citation
DOI: https://doi.org/10.1007/978-3-319-77404-6_60
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-77403-9
Online ISBN: 978-3-319-77404-6
eBook Packages: Computer ScienceComputer Science (R0)