Geodesic
Counting triangulations of planar point sets
The electronic journal of combinatorics, Tome 18 (2011) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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)$).
DOI : 10.37236/557
Classification : 05C35, 05C80, 05C07
Mots-clés : triangulations, counting, charging schemes, crossing-free graphs 
@article{10_37236_557,
     author = {Micha Sharir and Adam Sheffer},
     title = {Counting triangulations of planar point sets},
     journal = {The electronic journal of combinatorics},
     year = {2011},
     volume = {18},
     number = {1},
     doi = {10.37236/557},
     zbl = {1218.05072},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/557/}
}
TY  - JOUR
AU  - Micha Sharir
AU  - Adam Sheffer
TI  - Counting triangulations of planar point sets
JO  - The electronic journal of combinatorics
PY  - 2011
VL  - 18
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/557/
DO  - 10.37236/557
ID  - 10_37236_557
ER  - 
%0 Journal Article
%A Micha Sharir
%A Adam Sheffer
%T Counting triangulations of planar point sets
%J The electronic journal of combinatorics
%D 2011
%V 18
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/557/
%R 10.37236/557
%F 10_37236_557
Micha Sharir; Adam Sheffer. Counting triangulations of planar point sets. The electronic journal of combinatorics, Tome 18 (2011) no. 1. doi: 10.37236/557

Cité par Sources :