Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
The Graph Tessellation Cover Number: Extremal Bounds, Efficient Algorithms and Hardness Kapitel lesen Erstes Kapitel lesen

2018 | OriginalPaper | Buchkapitel

Transition Operations over Plane Trees

verfasst von : Torrie L. Nichols, Alexander Pilz, Csaba D. Tóth, Ahad N. Zehmakan

Erschienen in: LATIN 2018: Theoretical Informatics

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Rapid Mixing of k-Class Biased Permutations
Nächstes Kapitel Analysis of the Continued Logarithm Algorithm
Literatur
1.
Aichholzer, O., Asinowski, A., Miltzow, T.: Disjoint compatibility graph of non-crossing matchings of points in convex position. Electron. J. Comb. 22, P1 (2015)MathSciNetMATH
2.
Aichholzer, O., Aurenhammer, F., Huemer, C., Krasser, H.: Transforming spanning trees and pseudo-triangulations. Inf. Process. Lett. 97(1), 19–22 (2006)MathSciNetCrossRefMATH
3.
Aichholzer, O., Aurenhammer, F., Hurtado, F.: Sequences of spanning trees and a fixed tree theorem. Comput. Geom. 21(1–2), 3–20 (2002)MathSciNetCrossRefMATH
4.
Aichholzer, O., Reinhardt, K.: A quadratic distance bound on sliding between crossing-free spanning trees. Comput. Geom. 37(3), 155–161 (2007)MathSciNetCrossRefMATH
5.
6.
Aloupis, G., Barba, L., Langerman, S., Souvaine, D.L.: Bichromatic compatible matchings. Comput. Geom. 48(8), 622–633 (2015)MathSciNetCrossRefMATH
7.
8.
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)MathSciNetCrossRefMATH
9.
10.
Bose, P., Lubiw, A., Pathak, V., Verdonschot, S.: Flipping edge-labelled triangulations. Comput. Geom. (2017, in Press)
11.
Buchin, K., Razen, A., Uno, T., Wagner, U.: Transforming spanning trees: a lower bound. Comput. Geom. 42(8), 724–730 (2009)MathSciNetCrossRefMATH
12.
13.
Cayley, A.: A theorem on trees. Q. J. Math. 23, 376–378 (1889)MATH
14.
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)MathSciNetCrossRefMATH
15.
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)MathSciNetCrossRefMATH
16.
Chartrand, G., Saba, F., Zou, H.B.: Edge rotations and distance between graphs. Cas. Pest. Math. 110, 87–91 (1985)MathSciNetMATH
17.
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)MathSciNetCrossRefMATH
18.
19.
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)MathSciNetCrossRefMATH
20.
21.
Huemer, C., de Mier, A.: Lower bounds on the maximum number of non-crossing acyclic graphs. Europ. J. Comb. 48, 48–62 (2015)MathSciNetCrossRefMATH
22.
Ishaque, M., Souvaine, D.L., Tóth, C.D.: Disjoint compatible geometric matchings. Discret. Comput. Geom. 49, 89–131 (2013)MathSciNetCrossRefMATH
23.
Kanj, I.A., Sedgwick, E., Xia, G.: Computing the flip distance between triangulations. Discret. Comput. Geom. 58(2), 313–344 (2017)MathSciNetCrossRefMATH
24.
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)MathSciNetCrossRefMATH
25.
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)
26.
Lubiw, A., Pathak, V.: Flip distance between two triangulations of a point set is NP-complete. Comput. Geom. 49, 17–23 (2015)MathSciNetCrossRefMATH
27.
Oxley, J.G.: Matroid Theory. Oxford University Press, Oxford (1993)MATH
28.
29.
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)
30.
Sleator, D.D., Tarjan, R.E., Thurston, W.P.: Rotation distance, triangulations, and hyperbolic geometry. J. Am. Math. Soc. 1, 647–681 (1988)MathSciNetCrossRefMATH
31.
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)MathSciNetCrossRefMATH
Metadaten
Titel
Transition Operations over Plane Trees
verfasst von
Torrie L. Nichols
Alexander Pilz
Csaba D. Tóth
Ahad N. Zehmakan
Copyright-Jahr
2018
Buch
LATIN 2018: Theoretical Informatics

Print ISBN: 978-3-319-77403-9

Electronic ISBN: 978-3-319-77404-6

Copyright-Jahr: 2018

DOI
https://doi.org/10.1007/978-3-319-77404-6_60

Premium Partner

    Bildnachweise