×

Once punctured disks, non-convex polygons, and pointihedra. (English) Zbl 1396.05034

Summary: We explore several families of flip-graphs, all related to polygons or punctured polygons. In particular, we consider the topological flip-graphs of once punctured polygons which, in turn, contain all possible geometric flip-graphs of polygons with a marked point as embedded sub-graphs. Our main focus is on the geometric properties of these graphs and how they relate to one another. In particular, we show that the embeddings between them are strongly convex (or, said otherwise, totally geodesic). We find bounds on the diameters of these graphs, sometimes using the strongly convex embeddings and show that the topological flip-graph is Hamiltonian. These graphs relate to different polytopes, namely to type D associahedra and a family of secondary polytopes which we call pointihedra.

MSC:

05C12 Distance in graphs
57M15 Relations of low-dimensional topology with graph theory
05C10 Planar graphs; geometric and topological aspects of graph theory
32G15 Moduli of Riemann surfaces, Teichmüller theory (complex-analytic aspects in several variables)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aramayona, J.; Koberda, T.; Parlier, H., Injective maps between flip graphs, Ann. Inst. Fourier (Grenoble), 65, 2037-2055, (2015) · Zbl 1336.57028 · doi:10.5802/aif.2981
[2] Ceballos, C.; Pilaud, V., The diameter of type D associahedra and the non-leaving-face property, European J. Combin., 51, 109-124, (2016) · Zbl 1337.52010 · doi:10.1016/j.ejc.2015.04.006
[3] De Loera J., Rambau J., Santos F.: Triangulations: Structures for Algorithms and Applications Algorithms Comput. Math. Vol. 25. Springer, Berlin (2010) · Zbl 1207.52002 · doi:10.1007/978-3-642-12971-1
[4] Disarlo, V., Parlier, H.: The geometry of flip graphs and mapping class groups. Trans. Amer. Math. Soc. (to appear) · Zbl 1423.57004
[5] Gel’fand, I. M.; Zelevinsky, A. V.; Kapranov, M. M., Discriminants of polynomials in several variables and triangulations of Newton polyhedra, Leningrad Math. J., 2, 449-505, (1991) · Zbl 0741.14033
[6] Hurtado, F.; Noy, M., Graph of triangulations of a convex polygon and tree of triangulations, Comput. Geom., 13, 179-188, (1999) · Zbl 0948.68127 · doi:10.1016/S0925-7721(99)00016-4
[7] Hurtado, F.; Noy, M.; Urrutia, J., Flipping edges in triangulations, Discrete Comput. Geom., 22, 333-346, (1999) · Zbl 0939.68135 · doi:10.1007/PL00009464
[8] Lee, C. W., The associahedron and triangulations of the \(n\)-gon, European J. Combin., 10, 551-560, (1989) · Zbl 0682.52004 · doi:10.1016/S0195-6698(89)80072-1
[9] Lucas, J. M., The rotation graph of binary trees is Hamiltonian, J. Algorithms, 8, 503-535, (1987) · Zbl 0641.05015 · doi:10.1016/0196-6774(87)90048-4
[10] Parlier, H.; Pournin, L., Flip-graph moduli spaces of filling surfaces, J. Eur. Math. Soc., 19, 2697-2737, (2017) · Zbl 1369.05055 · doi:10.4171/JEMS/726
[11] Parlier, H.; Pournin, L., Modular flip-graphs of one-holed surfaces, European J. Combin., 67, 158-173, (2018) · Zbl 1371.05057 · doi:10.1016/j.ejc.2017.07.003
[12] Pournin, L., The diameter of associahedra, Adv. Math., 259, 13-42, (2014) · Zbl 1292.52011 · doi:10.1016/j.aim.2014.02.035
[13] Sleator, D.; Tarjan, R.; Thurston, W., Rotation distance, triangulations, and hyperbolic geometry, J. Amer. Math. Soc., 1, 647-681, (1988) · Zbl 0653.51017 · doi:10.1090/S0894-0347-1988-0928904-4
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.