A Canonical Tree Decomposition for Chirotopes Article Swipe

View

Related Concepts

Decomposition Tree (set theory) Computer science Mathematics Combinatorics Chemistry Organic chemistry

Mathilde Bouvel , Valentin Féray , Xavier Goaoc , Florent Koechlin ·

YOU? · · 2024 · Open Access · · DOI: https://doi.org/10.4230/lipics.socg.2024.23 · OA: W4405730368

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.