Abstract
Maximal (k+1)-crossing-free graphs on a planar point set in convex position, that is, k-triangulations, have received attention in recent literature, motivated by several interpretations of them.
We introduce a new way of looking at k-triangulations, namely as complexes of star polygons. With this tool we give new, direct proofs of the fundamental properties of k-triangulations, as well as some new results. This interpretation also opens up new avenues of research that we briefly explore in the last section.
Article PDF
Similar content being viewed by others
References
Ackerman, E., Tardos, G.: On the maximum number of edges in quasi-planar graphs. J. Am. Math. Soc. 114, 563–571 (2007)
Billera, L.J., Filliman, P., Sturmfels, B.: Constructions and complexity of secondary polytopes. Adv. Math. 83(2), 155–179 (1990)
Birman, J.S.: Braids, Links and Mapping Class Groups. Annals of Mathematical Studies, vol. 82. Princeton University Press, Princeton (1974)
Björner, A., Las Vergnas, M., Strumfelds, B., White, N., Ziegler, G.M.: Oriented Matroids, 2nd edn. Encyclopedia of Mathematics and its Applications, vol. 46. Cambridge University Press, Cambridge (1999)
Capoyleas, V., Pach, J.: A Turán-type theorem on chords of a convex polygon. J. Comb. Theory Ser. B 56(1), 9–15 (1992)
Coxeter, H.S.M.: Introduction to Geometry, 2nd edn. Wiley, New York (1969)
Coxeter, H.S.M.: Regular Polytopes, 3rd edn. Dover, New York (1973)
Desainte-Catherine, M., Viennot, G.: Enumeration of certain Young tableaux with bounded height. In: Combinatoire énumérative (Montreal, Que., 1985/Quebec, Que., 1985). Lecture Notes in Math., vol. 1234, pp. 58–67. Springer, New York (1986)
Dress, A.W.M., Klucznik, M., Koolen, J.H., Moulton, V.: \(2kn-\atop{2k+1}{2}\) : A note on extremal combinatorics of cyclic split systems. Sém. Lothar. Comb. 47, Article B47b, 17 pp. (electronic) (2001/02)
Dress, A.W.M., Koolen, J.H., Moulton, V.: On line arrangements in the hyperbolic plane. Eur. J. Comb. 23(5), 549–557 (2002)
Dress, A.W.M., Koolen, J.H., Moulton, V.: 4n−10. Ann. Comb. 8(4), 463–471 (2004)
Dress, A., Grünewald, S., Jonsson, J., Moulton, V.: The simplicial complex Δ n,k of k-compatible line arrangements in the hyperbolic plane. Part 1: The structure of Δ n,k . Preprint (2007)
Dress, A., Grünewald, S., Jonsson, J., Moulton, V.: The simplicial complex Δ n,k of k-compatible line arrangements in the hyperbolic plane. Part 2 (2008, in preparation)
Elizalde, S.: A bijection between 2-triangulations and pairs of non-crossing Dyck paths. J. Comb. Theory Ser. A 114(8), 1481–1503 (2007)
Fomin, S., Reading, N.: Root systems and generalized associahedra. In: Geometric Combinatorics. IAS/Park City Math. Ser., vol. 13, pp. 63–131. Am. Math. Soc., Providence (2007)
Graver, J.E.: Counting on Frameworks. The Dolciani Mathematical Expositions, vol. 25. The Mathematical Association of America, Washington (2001)
Graver, J.E., Servatius, B., Servatius, H.: Combinatorial Rigidity. Graduate Studies in Mathematics, vol. 2. American Mathematical Society, Providence (1993)
Herzog, J., Trung, N.V.: Gröbner bases and multiplicity of determinantal and Pfaffian ideals. Adv. Math. 96, 1–37 (1992)
Hohlweg, C., Lange, C.E.M.C.: Realizations of the associahedron and cyclohedron. Discrete Comput. Geom. 37, 517–543 (2007)
Ivanov, N.V.: Mapping class group. In: Daverman, R.J., Sher, R.B. (eds.) Handbook of Geometric Topology, pp. 523–633. North-Holland, Amsterdam (2002)
Jonsson, J.: Generalized triangulations of the n-gon. Unpublished manuscript (2003). An abstract was included in: Topological and Geometric Combinatorics, April 6th–April 12th, 2003, Mathematisches Forschungsinstitut Oberwolfach, Report No. 16/2003, http://www.mfo.de/programme/schedule/2003/15/Report16_2003.pdf
Jonsson, J.: Generalized triangulations and diagonal-free subsets of stack polyominoes. J. Comb. Theory Ser. A 112(1), 117–142 (2005)
Knuth, D.E.: Axioms and Hulls. Lecture Notes in Computer Science, vol. 606. Springer, New York (1992)
Krattenthaler, C.: Growth diagrams, and increasing and decreasing chains in fillings of Ferrers shapes. Adv. Appl. Math. 37(3), 404–431 (2006)
Lee, C.W.: The associahedron and triangulations of the n-gon. Eur. J. Comb. 10(6), 551–560 (1989)
Loday, J.-L.: Realization of the Stasheff polytope. Arch. Math. (Basel) 83(3), 267–278 (2004)
Lee, A., Streinu, I.: Pebble game algorithms and sparse graphs. Discrete Math. 308(8), 1425–1437 (2008)
Nakamigawa, T.: A generalization of diagonal flips in a convex polygon. Theor. Comput. Sci. 235(2), 271–282 (2000)
Pocchiola, M., Vegter, G.: Order types and visibility types of configurations of disjoint convex plane sets. Technical report, LIENS, Paris (January 1994)
Pocchiola, M., Vegter, G.: The visibility complex. Int. J. Comput. Geom. Appl. 6(3), 279–308 (1996)
Richter-Gebert, J., Ziegler, G.M.: Oriented matroids. In: Goodman, J.E., O’Rourke, J. (eds.) Handbook of Discrete and Computational Geometry. Ser. Discrete Math. Appl., pp. 111–132. CRC, New York (2004)
Rote, G., Santos, F., Streinu, I.: Expansive motions and the polytope of pointed pseudo-triangulations. In: Aronov, B., Basu, S., Pach, J., Sharir, M. (eds.) Discrete and Computational Geometry, The Goodman-Pollack Festschrift, Algorithms Combin., vol. 25, pp. 699–736. Springer, New York (2003)
Rote, G., Santos, F., Streinu, I.: Pseudo-triangulations—a survey. In: Goodman, J.E., Pach, J., Pollack, R. (eds.) Surveys on Discrete and Computational Geometry: Twenty Years Later. Contemporary Mathematics, vol. 453, pp. 343–410. Am. Math. Soc., Providence (2008)
Rubey, M.: Increasing and decreasing sequences in fillings of moon polyominoes. Adv. Appl. Math. (2007, to appear) [arXiv:math.CO/0604140]
Santos, F.: Geometric bistellar flips: The setting, the context and a construction. In: International Congress of Mathematicians, vol. III, pp. 931–962. Eur. Math. Soc., Zürich (2006)
Streinu, I., Theran, L.: Sparse hypergraphs and pebble game algorithms, Europ. J. Combin. (2007, to appear) [arXiv:math.CO/0703921]
Stanley, R.P.: Enumerative Combinatorics, vol. 2. Cambridge Studies in Advanced Mathematics, vol. 62. Cambridge University Press, Cambridge (1999)
Sleator, D.D., Tarjan, R.E., Thurston, W.P.: Rotation distance, triangulations, and hyperbolic geometry. J. Am. Math. Soc. 1(3), 647–681 (1988)
Whiteley, W.: Vertex splitting in isostatic frameworks. Struct. Topol. 16, 23–30 (1990)
Ziegler, G.M.: Lectures on Polytopes. Graduate Texts in Mathematics, vol. 152. Springer, New York (1995)
Author information
Authors and Affiliations
Corresponding author
Additional information
This paper was written while the first author was visiting the second one via an internship agreement between the École Normale Supérieure and the University of Cantabria. Research of both authors was also funded by grant MTM2005-08618-C02-02 of the Spanish Ministry of Education and Science.
A short version of this paper was presented at the FPSAC 08 conference.
Rights and permissions
About this article
Cite this article
Pilaud, V., Santos, F. Multitriangulations as Complexes of Star Polygons. Discrete Comput Geom 41, 284–317 (2009). https://doi.org/10.1007/s00454-008-9078-6
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-008-9078-6