Finding the order of a flip graph and how it relates to all possible triangulations of a graph

Question

I've recently run into the following problem:

Given a planar graph, how many possible triangulations are there?

I am using triangulations in the normal sense when applied to anything in geometric graph theory; namely, a triangulation is a simplicial tessellation of the convex hull of an arbitrary finite set of points in n-space. So, for a planar graph the triangulation of it would be what you expect, simply a decomposition of the graph into triangles.

I am aware that there is a theorem proved by C. Lawson that "The flip graph of any planar graph is connected", which essentially means that given a graph $G$, a triangulation $T_{1}$ of $G$ can be transformed into any other triangulation $T_{n}$ of $G$ in a finite number of flips. Now a natural question arises,

Let $G$ be an arbitrary planar graph and let $F_{G}$ be the flip graph of $G$. Is there a way to find the order of $F_{G}$ given $G$?

It seems to me that if there is a way to do this, based off of some properties of the graph, that it would tell you, by Lawson's Theorem, that the order of $F_{G}$ gives exactly how many possible triangulations of the graph there are.

Thus, my question is this:

For an arbitrary planar graph $G$, is it possible to find the order of $F_{G}$ without implicitly solving the problem of "how many possible triangulations of $G$ are there"?

For any way I know how to determine the order of a flip graph, I need to construct every possible triangulation first. Is there any result (references please) that shows how to determine the order of a flip graph without computing every possible triangulation first?

-

EDIT: I am looking specifically for some property of the graph, who knows, voronoi vertices and edges, some properties of the flip graph in configuration space, etc.

For example, based off of Euler's Formula $V-E+F=2$ it can easily be shown that the number of triangles in a triangulation is given by $t=2i+b-2$, where $b$ is the number of points in the convex hull and $i$ is the number of points in the interior. I am looking for something of this style. What properties of the graph or flip graph can I use to relate them to one another?

In response to Igor Rivin, I am not looking for random graph theoretic approaches or upper bounds to the problem. For example, a result by Francisco Santos and Raimund Seidel says that the number of triangulations of a point cloud, can be no larger than $$(59^i)(7^b)(6!)\left(\frac{(i+b)!}{(i+b+6)!}\right)$$ While, this is another approach to the problem, and albeit interesting, is not relevant to the question I am asking regarding the relationship between the order of a flip graph and the properties of a graph.

Answer 1

I am not sure your question admits of a definitive answer. Here is a suggestion. There has been a huge amount of work, and quite recent progress, on finding good bounds on the number of triangulations of a set of $n$ points. The current best upper bound is $30^n$, established by Sharir and Sheffer in "Counting triangulations of planar point sets," Electr. J. Comb., 18(1) (2011), P70. This paper, and related papers, make progress by finding structures inside graphs on those points, e.g., empty convex polygons, for which good or even exact bounds are known, the Catalan numbers in the case of convex polygons. So studying the techniques employed in these papers will shed light on your question. A place to start is the recent paper by Hoffmann, Sharir, Sheffer, Tóth, and Welzl, "Counting Plane Graphs: Flippability and its Applications" (arXiv arXiv:1012.0591). At one juncture they use a convex decomposition of $G$ to control the bound.
    
They prove this result:

Let $S$ be a set of $N$ points in the plane, so that its convex hull has $h$ vertices, and let $T$ be a triangulation of $S$. Then $T$ contains a convex decomposition of $S$ with at most $\frac{3}{2}N-h \le \frac{3}{2}N-3$ convex faces....this bound is tight.

For you, the size of a convex decomposition is a "property of $G$" which controls the number of triangulations of $G$, in your language, the "order of $F_G$."

Answer 2

I believe the following paper:

On random planar graphs, the number of planar graphs and their triangulations Deryk Osthus, , Hans Jürgen Prömel, , Anusch Taraz, (JCT(B), 2003) just estimates the number of triangulations without any flipping.