×

Graphs of triangulations and perfect matchings. (English) Zbl 1080.52001

Summary: Given a set \(P\) of points in general position in the plane, the graph of triangulations \({\mathcal T}(P)\) of \(P\) has a vertex for every triangulation of \(P\), and two of them are adjacent if they differ by a single edge exchange. We prove that the subgraph \({\mathcal T}_M(P)\) of \({\mathcal T}(P)\), consisting of all triangulations of \(P\) that admit a perfect matching, is connected. A main tool in our proof is a result of independent interest, namely that the graph \({\mathcal M}(P)\) that has as vertices the non-crossing perfect matchings of \(P\) and two of them are adjacent if their symmetric difference is a single non-crossing cycle, is also connected.

MSC:

52A10 Convex sets in \(2\) dimensions (including convex curves)
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Avis, D.: Generating rooted triangulations without repetitions, Algorithmica 16, 618–632 (1996) · Zbl 0860.68107
[2] Chartrand, G., Lesniak, L.: Graphs and digraphs, 3d edition, Chapman and Hall, 1996 · Zbl 0890.05001
[3] Galtier, J., Hurtado, F., Noy, M., Prenes S., Urrutia, J.: Simultaneous edge flipping in triangulations, Internat. J. Comput. Geom. Appl. 13(2), 113–133 (2003) · Zbl 1058.52005
[4] Hernando, C., Houle, M., Hurtado, F.: On local transformation of polygons with visibility properties, Theoretical Computer Science 289(2), 919–937 (2002) · Zbl 1061.68168
[5] Hernando, C., Hurtado, F., Noy, M.: Graphs of non-crossing perfect matchings, Graphs and Combinatorics 18, 517–532 (2002) · Zbl 1009.05110
[6] Hurtado F., Noy, M.: Graph of triangulations of a convex polygon and tree of triangulations, Computational Geometry: Theory and Applications 13, 179–188 (1999) · Zbl 0948.68127
[7] Hurtado, F., Noy, M., Urrutia, J.: Flipping edges in triangulations, Discrete and Computational Geometry 22, 333–346 (1999) · Zbl 0939.68135
[8] Sleator, D.D., Tarjan, R.E., Thurston, W.P.: Rotation distance, triangulations and hyperbolic geometry, J. Amer. Math. Soc. 1, 647–682 (1988) · Zbl 0653.51017
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.