On the Number of Drawings of a Combinatorial Triangulation
Open Access
- 21 January 2026
- journal article
- research article
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 42 (1) , 16
Abstract
In 1962, Tutte provided a formula for the number of combinatorial triangulations, that is, maximal planar graphs with a fixed triangular face and n additional vertices. In this note, we study in how many ways a combinatorial triangulation can be drawn as geometric triangulation, that is, with straight-line segments, on a given point set in the plane. Our central contribution is that there exist a combinatorial triangulation T and a point set S such that T can be drawn on S in at least $$\varOmega (1,31^n)$$ ways as different geometric triangulations. We also show an upper bound on the number of drawings of a combinatorial triangulation on the so-called double chain point set.
Keywords
All Related Versions
Funding Information
- Direcció General de Recerca, Generalitat de Catalunya (2021-SGR-00266)
- Ministerio de Ciencia e Innovación (PID2023-150725NB-I00)
This publication has 12 references indexed in Scilit:
- Chains, Koch Chains, and Point Sets with Many TriangulationsJournal of the ACM, 2023
- Lower bounds on the maximum number of non-crossing acyclic graphsEuropean Journal of Combinatorics, 2015
- Bounds on the Maximum Multiplicity of Some Common Geometric GraphsSIAM Journal on Discrete Mathematics, 2013
- On the number of pseudo-triangulations of certain point setsJournal of Combinatorial Theory, Series A, 2008
- On the Number of Plane Geometric GraphsGraphs and Combinatorics, 2007
- Random triangulations of planar point sets2006
- A better upper bound on the number of triangulations of a planar point setJournal of Combinatorial Theory, Series A, 2003
- Lower bounds on the number of crossing-free subgraphs of KNComputational Geometry, 2000
- Note – On the Number of Triangulations of Planar Point SetsCombinatorica, 1998
- Crossing-Free Subgraphs1982