A Canonical Tree Decomposition for Order Types, and Some Applications
We introduce and study a notion of decomposition of planar point sets (or rather of their chirotopes) as trees decorated by smaller chirotopes. This decomposition is based on the concept of mutually avoiding sets, and adapts in some sense the modular decomposition of graphs in the world of chirotopes. The associated tree always exists and is unique up to some appropriate constraints. We also show how to compute the number of triangulations of a chirotope efficiently, starting from its tree and the (weighted) numbers of triangulations of its parts.
Authors
- Xavier Goaoc (ORCID: https://orcid.org/0000-0002-4331-7169)
- Florent Koechlin (ORCID: https://orcid.org/0000-0002-5576-4847)
- Valentin Féray (ORCID: https://orcid.org/0000-0002-9060-0696)
- Mathilde Bouvel
Institutions
- Centre National de la Recherche Scientifique (FR)
- Institut Élie Cartan de Lorraine (FR)
- Sorbonne Université (FR)
- Université Sorbonne Paris Nord (FR)
- Laboratoire Lorrain de Recherche en Informatique et ses Applications (FR)
- Laboratoire de physique des lasers (FR)
- Laboratoire d'Informatique de Paris-Nord (FR)
- Université de Lorraine (FR)
Publication Details
- Journal
- SIAM Journal on Discrete Mathematics
- Published
- 2025-10-28
- DOI
- https://doi.org/10.1137/24m1672201
- Primary Topic
- Advanced Graph Theory Research
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- Institut national de recherche en informatique et en automatique (INRIA)
- Agence Nationale de la Recherche