Computer Science – Discrete Mathematics
Scientific paper
2010-12-02
Computer Science
Discrete Mathematics
Scientific paper
We generalize the notions of flippable and simultaneously flippable edges in a triangulation of a set S of points in the plane to so-called \emph{pseudo-simultaneously flippable edges}. Such edges are related to the notion of convex decompositions spanned by S. 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.7022^N) * tr(N) = O(141.07^N) spanning trees, and O(5.3514^N) * tr(N) = O(160.55^N) forests. We also obtain upper bounds for the number of crossing-free straight-edge graphs that have cN, fewer than cN, or more than cN edges, for any constant parameter c, in terms of c and N.
Hoffmann Michael
Sharir Micha
Sheffer A. A.
Tóth Csaba D.
Welzl Emo
No associations
LandOfFree
Counting Plane Graphs: Flippability and its Applications does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Counting Plane Graphs: Flippability and its Applications, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Counting Plane Graphs: Flippability and its Applications will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-513202