Skip to main content
Image links broken; now fixed.
Source Link
Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958

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.
    Emo Fig.7 http://cs.smith.edu/%7Eorourke/MathOverflow/EmoFig7.jpgEmo Fig.7
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$."

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.
    Emo Fig.7 http://cs.smith.edu/%7Eorourke/MathOverflow/EmoFig7.jpg
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$."

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.
    Emo Fig.7
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$."

Included a figure from the Welzl paper.
Source Link
Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958

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][1]arXiv arXiv:1012.0591). At one juncture they use a convex decomposition of $G$ to control the bound.
    Emo Fig.7 http://cs.smith.edu/%7Eorourke/MathOverflow/EmoFig7.jpg
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$." [1]: http://arxiv.org/abs/1012.0591

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][1]). 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$." [1]: http://arxiv.org/abs/1012.0591

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.
    Emo Fig.7 http://cs.smith.edu/%7Eorourke/MathOverflow/EmoFig7.jpg
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$."

Source Link
Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958

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][1]). 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$." [1]: http://arxiv.org/abs/1012.0591