@inbook {IOPORT.05938300,
    author       = {Hoffmann, Michael and Sharir, Micha and Sheffer, Adam and T\'oth, Csaba D. and Welzl, Emo},
    title        = {Counting plane graphs: flippability and its applications.},
    year         = {2011},
    booktitle    = {Algorithms and data structures. 12th international symposium, WADS 2011, New York, NY, USA, August 15--17, 2011. Proceedings},
    isbn         = {978-3-642-22299-3},
    pages        = {524-535},
    publisher    = {Berlin: Springer},
    doi          = {10.1007/978-3-642-22300-6_44},
    abstract     = {Summary: 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} \cdot tr(N) < 207.85^{N}$ crossing-free straight-edge graphs, $O(4.8795^{N}) \cdot tr(N) = O(146.39^{N})$ spanning trees, and $O(5.4723^{N}) \cdot 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$.},
    identifier   = {05938300},
}