Counting Plane Graphs: Flippability and Its Applications

We generalize the notions of flippable and simultaneously flippable edges in a triangulation of a set

S

of points in the plane into so called

pseudo-simultaneously flippable edges

.

We prove a worst-case tight lower bound for the number of pseudo-simultaneously flippable edges in a triangulation in terms of the number of vertices. We use this bound for deriving new upper bounds for the maximal number of crossing-free straight-edge graphs that can be embedded on any fixed set of

N

points in the plane. We obtain new upper bounds for the number of spanning trees and forests as well. Specifically, let

tr

(

N

) denote the maximum number of triangulations on a set of

N

points in the plane. Then we show (using the known bound

tr

(

N

) < 30

N

) that any

N

-element point set admits at most 6.9283

N

·

tr

(

N

) < 207.85

N

crossing-free straight-edge graphs,

O

(4.8795

N

) ·

tr

(

N

) = 

O

(146.39

N

) spanning trees, and

O

(5.4723

N

) ·

tr

(

N

) = 

O

(164.17

N

) forests. We also obtain upper bounds for the number of crossing-free straight-edge graphs that have fewer than

cN

or more than

cN

edges, for a constant parameter

c

, in terms of

c

and

N

.