×

Blockers for triangulations of a convex polygon and a geometric maker-breaker game. (English) Zbl 1450.05013

Summary: Let \(G\) be a complete convex geometric graph whose vertex set \(P\) forms a convex polygon \(C\), and let \(\mathcal{F}\) be a family of subgraphs of \(G\). A blocker for \(\mathcal{F}\) is a set of diagonals of \(C\), of smallest possible size, that contains a common edge with every element of \(\mathcal{F} \). Previous works determined the blockers for various families \(\mathcal{F}\) of non-crossing subgraphs, including the families of all perfect matchings, all spanning trees, all Hamiltonian paths, etc.
In this paper we present a complete characterization of the family \(\mathcal{B}\) of blockers for the family \(\mathcal{T}\) of triangulations of \(C\). In particular, we show that \(|\mathcal{B}|=F_{2n-8} \), where \(F_k\) is the \(k\)’th element in the Fibonacci sequence and \(n=|P|\).
We use our characterization to obtain a tight result on a geometric Maker-Breaker game in which the board is the set of diagonals of a convex \(n\)-gon \(C\) and Maker seeks to occupy a triangulation of \(C\). We show that in the \((1:1)\) triangulation game, Maker can ensure a win within \(n-3\) moves, and that in the \((1:2)\) triangulation game, Breaker can ensure a win within \(n-3\) moves. In particular, the threshold bias for the game is \(2\).

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
05C12 Distance in graphs
05C57 Games on graphs (graph-theoretic aspects)
91A43 Games involving graphs
52B05 Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] N. A. Ali, G. L. Chia, H. M. Trao, and A. Kilicman. Triangulability of convex graphs and convex skewness, manuscript, 2016.arXiv:1611.09033.
[2] J. Beck. Remarks on positional games. I.Acta Math. Acad. Sci. Hungar., 40(1-2):65- 71, 1982. · Zbl 0515.90100
[3] P. Brass, G. K´arolyi, and P. Valtr. A Tur´an-type extremal theory of convex geometric graphs. In B. Aronov, S. Basu, J. Pach, and M. Sharir (eds.),Discrete and computational geometry – the Goodman-Pollack Festschrift, pp. 275-300. Springer, 2003. · Zbl 1074.05048
[4] V. Capoyleas and J. Pach. A Tur´an-type theorem on chords of a convex polygon.J. Comb. Theory, Ser. B, 56(1):9-15, 1992. · Zbl 0783.05032
[5] M. Carr and S. Devadoss. Coxeter complexes and graph associahedra.Topology Appl., 153:2155-2168, 2006. · Zbl 1099.52001
[6] J. A. De Loera, J. Rambau, and F. Santos. Triangulations in mathematics. In J. A. De Loera, J. Rambau, and F. Santos (eds.),Triangulations - Structures for Algorithms and Applications, pp. 1-41. Springer, 2010. · Zbl 1207.52002
[7] A. Dress, J. H. Koolen, and V. Moulton. On line arrangements in the hyperbolic plane.Europ. J. Combin., 23:549-557, 2002. · Zbl 1023.52007
[8] P. Erd˝os and J. L. Selfridge. On a combinatorial game.J. Comb. Theory, Ser. A, 14(3):298-301, 1973. · Zbl 0293.05004
[9] S. Fomin and A. Zelevinsky. Y-systems and generalized associahedra.Ann. Math., 158(3):977-1018, 2003. · Zbl 1057.52003
[10] F. Harary and A. J. Schwenk. The number of caterpillars.Disc. Math., 6(4):359-365, 1973. · Zbl 0266.05102
[11] D. Hefetz, M. Krivelevich, M. Stojakovic, and T. Szab´o. Fast winning strategies in avoider-enforcer games.Graphs Combin., 25(4):533-544, 2009. · Zbl 1181.91044
[12] M. Carmen Hernando.Complejidad de Estructuras Geom´etricas y Combinatorias. PhD thesis, Universitat Polit´ectnica de Catalunya, 1999. Available online at:http: //www.tdx.cat/TDX-0402108-120036.
[13] M. Carmen Hernando, F. Hurtado, A. M´arquez, M. Mora, and M. Noy. Geometric tree graphs of points in convex position.Disc. Appl. Math., 93(1):51-66, 1999. · Zbl 0930.05032
[14] F. Hurtado and M. Noy. Graph of triangulations of a convex polygon and tree of triangulations.Comput. Geom., 13(3):179-188, 1999. · Zbl 0948.68127
[15] J. M. Keil and T. S. Vassilev. Algorithms for optimal area triangulations of a convex polygon.Comput. Geom., 35(3):173-187, 2006. · Zbl 1102.65026
[16] C. Keller and M. A. Perles. On the smallest sets blocking simple perfect matchings in a convex geometric graph.Israel J. Math., 187(1):465-484, 2012. · Zbl 1253.05114
[17] C. Keller and M. A. Perles. Characterization of co-blockers for simple perfect matchings in a convex geometric graph.Discret. Comput. Geom., 50(2):491-502, 2013. · Zbl 1272.05159
[18] C. Keller and M. A. Perles. Blockers for simple Hamiltonian paths in convex geometric graphs of even order.Discret. Comput. Geom., 60(1):1-8, 2018. · Zbl 1392.05065
[19] C. Keller, M. A. Perles, E. Rivera-Campo, and V. Urrutia-Galicia. Blockers for noncrossing spanning trees in complete geometric graphs. In J. Pach (ed.),Thirty Essays on Geometric Graph Theory, pp. 383-397. Springer, 2013. · Zbl 1272.05026
[20] G. T. Klincsek. Minimal triangulations of polygonal domains.Ann. Disc. Math., 9:121-123, 1980. · Zbl 0452.05002
[21] M. Krivelevich. Positional games.Proc. Internat. Congress Math. (ICM), 4:355-379, 2014. · Zbl 1373.05119
[22] Y. S. Kupitz.Extremal problems in combinatorial geometry. Number 53. Matematisk institut, Aarhus universitet, 1979. · Zbl 0414.05029
[23] Y. S. Kupitz and M. A. Perles. Extremal theory for convex matchings in convex geometric graphs.Discret. Comput. Geom., 15(2):195-220, 1996. · Zbl 0845.05056
[24] C. W. Lee. The associahedron and triangulations of then-gon.European J. Combin., 10(6):551 - 560, 1989. · Zbl 0682.52004
[25] V. Pilaud and V. Pons. Permutrees.Alg. Combin., 1(2):173-224, 2018. · Zbl 1388.05039
[26] D. D. Sleator, R. E. Tarjan, and W. P. Thurston. Rotation distance, triangulations, and hyperbolic geometry.J. Amer. Math. Soc., 1(3):647-681, 1988. · Zbl 0653.51017
[27] J. Stasheff. Homotopy associativity of H-spaces.Trans. Amer. Math. Soc., 108:275- 292, 1963. · Zbl 0114.39402
[28] D.
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.