Counting Plane Graphs: Flippability and Its Applications

Michael Hoffmann (), André Schulz (), Micha Sharir (), Adam Sheffer (), Csaba D. Tóth () and Emo Welzl ()
Additional contact information
Michael Hoffmann: ETH Zürich, Institute of Theoretical Computer Science
André Schulz: Universität Münster, Institut für Mathematische Logik und Grundlagenforschung
Micha Sharir: Tel Aviv University, School of Computer Science
Adam Sheffer: Tel Aviv University, School of Computer Science
Csaba D. Tóth: University of Calgary, Department of Mathematics and Statistics
Emo Welzl: ETH Zürich, Institute of Theoretical Computer Science

A chapter in Thirty Essays on Geometric Graph Theory, 2013, pp 303-325 from Springer

Abstract: Abstract We generalize the notions of flippable and simultaneously flippable edges in a triangulation of a set S of points in the plane to 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 $$\mathsf{tr}(N)$$ denote the maximum number of triangulations on a set of N points in the plane. Then we show [using the known bound $$\mathsf{tr}(N)

Keywords: Convex Hull; Span Tree; Planar Graph; Convex Polygon; Interior Vertex (search for similar items in EconPapers)
Date: 2013
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4614-0110-0_16

Ordering information: This item can be ordered from
http://www.springer.com/9781461401100

DOI: 10.1007/978-1-4614-0110-0_16

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().