Counting Triangulations of Planar Point Sets

• DOI: 10.37236/557
• Publication Date: 2020-01-11T03:51:58Z
• Authors: Micha Sharir; Adam Sheffer
• Keywords: FOS: Computer and information sciences; Discrete Mathematics (cs.DM); G.2.1; G.2.2; 0102 computer and information sciences; F.2.2; F.2.2; G.2.1; G.2.2; 01 natural sciences; Computer Science - Discrete Mathematics

We study the maximal number of triangulations that a planar set of $n$ points can have, and show that it is at most $30^n$. This new bound is achieved by a careful optimization of the charging scheme of Sharir and Welzl (2006), which has led to the previous best upper bound of $43^n$ for the problem. Moreover, this new bound is useful for bounding the number of other types of planar (i.e., crossing-free) straight-line graphs on a given point set. Specifically, it can be used to derive new upper bounds for the number of planar graphs ($207.84^n$), spanning cycles ($O(68.67^n)$), spanning trees ($O(146.69^n)$), and cycle-free graphs ($O(164.17^n)$).