Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Multi-triangulations ...
Conference paper

Multi-triangulations as complexes of star polygons

Vincent Pilaud ORCID (1), Francisco Santos ORCID (2) (3)
(1) École normale supérieure - Paris
(2) Universidad de Cantabria [Santander]
(3) Universidad de Cantabria [Santander] = University of Cantabria [Spain] = Université de Cantabrie [Espagne]
Download article
Open on HAL
Imported on
May 10, 2017
Published on
December 31, 2007
Last modified on
March 31, 2025
Volume
DMTCS Proceedings vol. AJ, 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008)
Proceedings
DOI
10.46298/dmtcs.3642
License
https://about.hal.science/hal-authorisation-v1
Indicators
763
Views
784
Downloads

Multi-triangulations as complexes of star polygons

Vincent Pilaud ORCID (1), Francisco Santos ORCID (2) (3)
(1) École normale supérieure - Paris
(2) Universidad de Cantabria [Santander]
(3) Universidad de Cantabria [Santander] = University of Cantabria [Spain] = Université de Cantabrie [Espagne]
Abstract
English
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.
French
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.
Keywords
  • [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • generalized triangulation
  • crossing-free graph
  • star polygon
Cited by

Source: OpenCitations

  • A Hopf algebra of subword complexes

    Advances in Mathematics

    Authors : Nantel Bergeron ORCID, Cesar Ceballos ORCID

    Journal reference : Volume 305, 2016, pp. 1163-1201

    DOI : 10.1016/j.aim.2016.10.007
  • Dichotomy of the Addition of Natural Numbers

    Progress in mathematics

    Authors : Jean-Louis Loday

    Journal reference : Volume , 2012, pp. 65-79

    DOI : 10.1007/978-3-0348-0405-9_4
  • Wigglyhedra

    Mathematische Zeitschrift

    Authors : Asilata Bapat ORCID, Vincent Pilaud

    Journal reference : Volume 310, 2025, pp.

    DOI : 10.1007/s00209-025-03688-9
  • Multitriangulations and Tropical Pfaffians

    UCrea (University of Cantabria)

    Authors : Luis Crespo Ruiz ORCID, Francisco Santos ORCID

    Journal reference : Volume 8, 2024, pp. 302-332

    DOI : 10.1137/22m1527507
  • One Brick at a Time: A Survey of Inductive Constructions in Rigidity Theory

    Fields Institute communications

    Authors : A. Nixon ORCID, E. Ross ORCID

    Journal reference : Volume , 2014, pp. 303-324

    DOI : 10.1007/978-1-4939-0781-6_15
  • Multitriangulations, Pseudotriangulations and Primitive Sorting Networks

    Discrete & Computational Geometry

    Authors : Vincent Pilaud ORCID, Michel Pocchiola

    Journal reference : Volume 48, 2012, pp. 142-191

    DOI : 10.1007/s00454-012-9408-6
  • Fan Realizations for Some 2-Associahedra

    arXiv (Cornell University)

    Authors : Thibault Manneville

    Journal reference : Volume 27, 2017, pp. 377-394

    DOI : 10.1080/10586458.2017.1289866
  • The brick polytope of a sorting network

    European Journal of Combinatorics

    Authors : Vincent Pilaud ORCID, Francisco Santos ORCID

    Journal reference : Volume 33, 2012, pp. 632-662

    DOI : 10.1016/j.ejc.2011.12.003
  • The diameter of associahedra

    Advances in Mathematics

    Authors : Lionel Pournin ORCID

    Journal reference : Volume 259, 2014, pp. 13-42

    DOI : 10.1016/j.aim.2014.02.035
  • Fan Realizations of Type $$A$$ A Subword Complexes and Multi-associahedra of Rank 3

    arXiv (Cornell University)

    Authors : Nantel Bergeron ORCID, Cesar Ceballos ORCID, Jean-Philippe Labbé ORCID

    Journal reference : Volume 54, 2015, pp. 195-231

    DOI : 10.1007/s00454-015-9691-0
  • Maximal 0-1-fillings of moon polyominoes with restricted chain lengths and rc-graphs

    Discrete Mathematics & Theoretical Computer Science

    Authors : Martin Rubey

    Journal reference : Volume DMTCS Proceedings vol. AO,..., 2011, pp.

    DOI : 10.46298/dmtcs.2957
  • Brick polytopes, lattice quotients, and Hopf algebras

    arXiv (Cornell University)

    Authors : Vincent Pilaud ORCID

    Journal reference : Volume 155, 2017, pp. 418-457

    DOI : 10.1016/j.jcta.2017.11.014
  • Realizations of Multiassociahedra via Rigidity

    Discrete & Computational Geometry

    Authors : Luis Crespo Ruiz ORCID, Francisco Santos ORCID

    Journal reference : Volume 73, 2024, pp. 973-1015

    DOI : 10.1007/s00454-024-00698-y
  • Subword complexes, cluster complexes, and generalized multi-associahedra

    Journal of Algebraic Combinatorics

    Authors : Cesar Ceballos, Jean-Philippe Labbé, Christian Stump

    Journal reference : Volume 39, 2013, pp. 17-51

    DOI : 10.1007/s10801-013-0437-x
  • Maximal 0–1-fillings of moon polyominoes with restricted chain lengths and rc-graphs

    Advances in Applied Mathematics

    Authors : Martin Rubey

    Journal reference : Volume 48, 2011, pp. 290-305

    DOI : 10.1016/j.aam.2011.05.005
  • Realizing the Associahedron: Mysteries and Questions

    Associahedra, Tamari Lattices and Related Structures

    Authors : Cesar Ceballos ORCID, Günter M. Ziegler ORCID

    Journal reference : Volume , 2012, pp. 119-127

    DOI : 10.1007/978-3-0348-0405-9_7
  • Posets and Spaces of $k$-Noncrossing RNA Structures

    SIAM Journal on Discrete Mathematics

    Authors : Vincent Moulton ORCID, Taoyang Wu ORCID

    Journal reference : Volume 36, 2022, pp. 1586-1611

    DOI : 10.1137/21m1413316
  • Brick polytopes of spherical subword complexes and generalized associahedra

    Advances in Mathematics

    Authors : Vincent Pilaud ORCID, Christian Stump ORCID

    Journal reference : Volume 276, 2015, pp. 1-61

    DOI : 10.1016/j.aim.2015.02.012
  • Celebrating Loday’s associahedron

    Archiv der Mathematik

    Authors : Vincent Pilaud ORCID, Francisco Santos ORCID, Günter M. Ziegler ORCID

    Journal reference : Volume 121, 2023, pp. 559-601

    DOI : 10.1007/s00013-023-01895-6
  • The size of 3-compatible, weakly compatible split systems

    Journal of Applied Mathematics and Computing

    Authors : Stefan Grünewald ORCID, Jack H. Koolen ORCID, Vincent Moulton ORCID, Taoyang Wu ORCID

    Journal reference : Volume 40, 2012, pp. 249-259

    DOI : 10.1007/s12190-012-0546-z
  • Stickiness in chaotic billiards with n-fold symmetry

    The European Physical Journal Special Topics

    Authors : R. B. do Carmo, T. Araújo Lima

    Journal reference : Volume , 2026, pp.

    DOI : 10.1140/epjs/s11734-026-02141-0
  • Maximal Fillings of Moon Polyominoes, Simplicial Complexes, and Schubert Polynomials

    The Electronic Journal of Combinatorics

    Authors : Luis Serrano ORCID, Christian Stump ORCID

    Journal reference : Volume 19, 2012, pp.

    DOI : 10.37236/1167
  • The diameter of type D associahedra and the non-leaving-face property

    European Journal of Combinatorics

    Authors : Cesar Ceballos ORCID, Vincent Pilaud ORCID

    Journal reference : Volume 51, 2015, pp. 109-124

    DOI : 10.1016/j.ejc.2015.04.006
  • A new perspective on k-triangulations

    Journal of Combinatorial Theory Series A

    Authors : Christian Stump ORCID

    Journal reference : Volume 118, 2011, pp. 1794-1800

    DOI : 10.1016/j.jcta.2011.03.001
  • Analytic combinatorics of chord and hyperchord diagrams with k crossings

    Advances in Applied Mathematics

    Authors : Vincent Pilaud ORCID, Juanjo Rué ORCID

    Journal reference : Volume 57, 2014, pp. 60-100

    DOI : 10.1016/j.aam.2014.04.001
  • EL-Labelings and Canonical Spanning Trees for Subword Complexes

    arXiv (Cornell University)

    Authors : Vincent Pilaud ORCID, Christian Stump ORCID

    Journal reference : Volume , 2013, pp. 213-248

    DOI : 10.1007/978-3-319-00200-2_13
Preview
Loading PDF preview...