  Let $P$ be a set of $n$ points in the plane. A crossing-free structure on $P$
is a plane graph with vertex set $P$. Examples of crossing-free structures
include triangulations of $P$, spanning cycles of $P$, also known as
polygonalizations of $P$, among others. In this paper we develop a general
technique for computing the number of crossing-free structures of an input set
$P$. We apply the technique to obtain algorithms for computing the number of
triangulations, matchings, and spanning cycles of $P$. The running time of our
algorithms is upper bounded by $n^{O(k)}$, where $k$ is the number of onion
layers of $P$. In particular, for $k = O(1)$ our algorithms run in polynomial
time. In addition, we show that our algorithm for counting triangulations is
never slower than $O^{*}(3.1414^{n})$, even when $k = \Theta(n)$. Given that
there are several well-studied configurations of points with at least
$\Omega(3.464^{n})$ triangulations, and some even with $\Omega(8^{n})$
triangulations, our algorithm asymptotically outperforms any enumeration
algorithm for such instances. In fact, it is widely believed that any set of
$n$ points must have at least $\Omega(3.464^{n})$ triangulations. If this is
true, then our algorithm is strictly sub-linear in the number of triangulations
counted. We also show that our techniques are general enough to solve the
"Restricted-Triangulation-Counting-Problem", which we prove to be $W[2]$-hard
in the parameter $k$. This implies a "no free lunch" result: In order to be
fixed-parameter tractable, our general algorithm must rely on additional
properties that are specific to the considered class of structures.
