Multi-triangulations as complexes of star polygons

Vincent Pilaud; Francisco Santos

doi:10.46298/dmtcs.3642

Vincent Pilaud ; Francisco Santos - Multi-triangulations as complexes of star polygons

dmtcs:3642 - Discrete Mathematics & Theoretical Computer Science, January 1, 2008, DMTCS Proceedings vol. AJ, 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008) - https://doi.org/10.46298/dmtcs.3642

Multi-triangulations as complexes of star polygonsConference paper

Authors: Vincent Pilaud ¹; Francisco Santos ^2,³

[en]
A $k$-triangulation of a convex polygon is a maximal set of diagonals so that no $k+1$ of them mutually cross. $k$-triangulations have received attention in recent literature, with motivation coming from several interpretations of them. We present a new way of looking at $k$-triangulations, where certain star polygons naturally generalize triangles for $k$-triangulations. With this tool we give new, direct proofs of the fundamental properties of $k$-triangulations (number of edges, definition of flip). This interpretation also opens up new avenues of research that we briefly explore in the last section.

[fr]
Une $k$-triangulation d'un polygone convexe est un ensemble maximal de diagonales ne contenant pas $k+1$ arêtes qui se croisent deux à deux. Les $k$-triangulations ont été récemment étudiées sous divers aspects dans la littérature. On présente ici un nouveau point de vue sur les $k$-triangulations, en introduisant certains polygones étoilés comme généralisation des triangles pour les $k$-triangulations. En utilisant ce nouvel outil, on donne des preuves directes des propriétés fondamentales des $k$-triangulations (nombre d'arêtes, définition du flip). Notre point de vue ouvre par ailleurs de nouveaux horizons de recherche que l'on présente rapidement dans la dernière partie.

https://doi.org/10.46298/dmtcs.3642

Source: HAL:hal-01185178v1

Volume: DMTCS Proceedings vol. AJ, 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008)

Section: Proceedings

Published on: January 1, 2008

Imported on: May 10, 2017

Keywords: [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [en] generalized triangulation, crossing-free graph, star polygon

Bibliographic References

22 Documents citing this article

Luis Crespo Ruiz;Francisco Santos, 2024, Realizations of Multiassociahedra via Rigidity, Discrete & Computational Geometry, 73, 4, pp. 973-1015, 10.1007/s00454-024-00698-y, https://doi.org/10.1007/s00454-024-00698-y.

Luis Crespo Ruiz;Francisco Santos, 2024, Multitriangulations and Tropical Pfaffians, SIAM Journal on Applied Algebra and Geometry, 8, 2, pp. 302-332, 10.1137/22m1527507.

Vincent Pilaud;Francisco Santos;Günter M. Ziegler, 2023, Celebrating Loday’s associahedron, Archiv der Mathematik, 121, 5-6, pp. 559-601, 10.1007/s00013-023-01895-6, https://doi.org/10.1007/s00013-023-01895-6.

Vincent Moulton;Taoyang Wu, 2022, Posets and Spaces of $k$-Noncrossing RNA Structures, SIAM Journal on Discrete Mathematics, 36, 3, pp. 1586-1611, 10.1137/21m1413316.

Thibault Manneville;Thibault Manneville, 2017, Fan Realizations for Some 2-Associahedra, arXiv (Cornell University), 27, 4, pp. 377-394, 10.1080/10586458.2017.1289866, http://arxiv.org/abs/1608.08491.

Nantel Bergeron;Cesar Ceballos, 2016, A Hopf algebra of subword complexes, arXiv (Cornell University), 305, pp. 1163-1201, 10.1016/j.aim.2016.10.007, http://arxiv.org/abs/1508.01465.

Cesar Ceballos;Vincent Pilaud, 2015, The diameter of type D associahedra and the non-leaving-face property, arXiv (Cornell University), 51, pp. 109-124, 10.1016/j.ejc.2015.04.006, http://arxiv.org/abs/1406.0368.

Nantel Bergeron;Cesar Ceballos;Jean-Philippe Labbé, 2015, Fan Realizations of Type $$A$$ A Subword Complexes and Multi-associahedra of Rank 3, arXiv (Cornell University), 54, 1, pp. 195-231, 10.1007/s00454-015-9691-0, http://arxiv.org/abs/1404.7380.

Vincent Pilaud;Christian Stump, 2015, Brick polytopes of spherical subword complexes and generalized associahedra, arXiv (Cornell University), 276, pp. 1-61, 10.1016/j.aim.2015.02.012, http://arxiv.org/abs/1111.3349.

A. Nixon;E. Ross, 2014, One Brick at a Time: A Survey of Inductive Constructions in Rigidity Theory, Fields Institute communications, pp. 303-324, 10.1007/978-1-4939-0781-6_15.

Lionel Pournin, 2014, The diameter of associahedra, arXiv (Cornell University), 259, pp. 13-42, 10.1016/j.aim.2014.02.035, http://arxiv.org/abs/1207.6296.

Vincent Pilaud;Juanjo Rué, 2014, Analytic combinatorics of chord and hyperchord diagrams with k crossings, arXiv (Cornell University), 57, pp. 60-100, 10.1016/j.aam.2014.04.001, http://arxiv.org/abs/1307.6440.

Cesar Ceballos;Jean-Philippe Labbé;Christian Stump, 2013, Subword complexes, cluster complexes, and generalized multi-associahedra, Journal of Algebraic Combinatorics, 39, 1, pp. 17-51, 10.1007/s10801-013-0437-x, https://doi.org/10.1007/s10801-013-0437-x.

Vincent Pilaud;Christian Stump, 2013, EL-Labelings and Canonical Spanning Trees for Subword Complexes, arXiv (Cornell University), pp. 213-248, 10.1007/978-3-319-00200-2_13, http://arxiv.org/abs/1210.1435.

Cesar Ceballos;Günter M. Ziegler, 2012, Realizing the Associahedron: Mysteries and Questions, Associahedra, Tamari Lattices and Related Structures, pp. 119-127, 10.1007/978-3-0348-0405-9_7.

Jean-Louis Loday, 2012, Dichotomy of the Addition of Natural Numbers, Progress in mathematics, pp. 65-79, 10.1007/978-3-0348-0405-9_4.

Luis Serrano;Christian Stump, 2012, Maximal Fillings of Moon Polyominoes, Simplicial Complexes, and Schubert Polynomials, The Electronic Journal of Combinatorics, 19, 1, 10.37236/1167, https://doi.org/10.37236/1167.

Stefan Grünewald;Jack H. Koolen;Vincent Moulton;Taoyang Wu, 2012, The size of 3-compatible, weakly compatible split systems, Scopus, 40, 1-2, pp. 249-259, 10.1007/s12190-012-0546-z, http://scholarbank.nus.edu.sg/handle/10635/104354.

Vincent Pilaud;Francisco Santos, 2012, The brick polytope of a sorting network, arXiv (Cornell University), 33, 4, pp. 632-662, 10.1016/j.ejc.2011.12.003, http://arxiv.org/abs/1103.2731.

Vincent Pilaud;Michel Pocchiola, 2012, Multitriangulations, Pseudotriangulations and Primitive Sorting Networks, Discrete & Computational Geometry, 48, 1, pp. 142-191, 10.1007/s00454-012-9408-6, https://doi.org/10.1007/s00454-012-9408-6.

Christian Stump, 2011, A new perspective on k-triangulations, Journal of Combinatorial Theory Series A, 118, 6, pp. 1794-1800, 10.1016/j.jcta.2011.03.001.

Martin Rubey, 2011, Maximal 0–1-fillings of moon polyominoes with restricted chain lengths and rc-graphs, Advances in Applied Mathematics, 48, 2, pp. 290-305, 10.1016/j.aam.2011.05.005.

Sources : OpenCitations, OpenAlex & Crossref

Share and export

Consultation statistics

This page has been seen 421 times.

This article's PDF has been downloaded 395 times.