\documentclass[12pt]{article}
\usepackage{amsmath,mathrsfs,bbm}
\usepackage{amssymb}
\textwidth=4.825in
\overfullrule=0pt
\thispagestyle{empty}
\begin{document}
\noindent
%
%
{\bf Micha Sharir and Adam Sheffer}
%
%
\medskip
\noindent
%
%
{\bf Counting Triangulations of Planar Point Sets}
%
%
\vskip 5mm
\noindent
%
%
%
%
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)$).
\end{document}