On two lower bound constructions.
Adrian Dumitrescu · 1999
We address two problems. In the first, we refine the analysis of a lower bound construction of a point set having many non-crossing spanning trees. We also give more precise upper bounds on the maximum number of non-crossing spanning trees, perfect matchings and simple polygons of a planar point set. In the second, we give an improved lower bound construction for the d-interval problem. 1 Non-crossing subgraphs -- an introduction Consider a set of n points in the plane and the straightline drawing of the complete graph Kn they define. A subgraph of Kn in this drawing is called non-crossing (or crossing-free) if its edges intersect only at common vertices. Ajtai, Chvatal, Newborn and Szemeredi [ACNS82] proved that the number of non-crossing subgraphs of any drawing of Kn (even without the rectilinear restriction on edges) is bounded from above by 10 13n . This result was a consequence of a lower bound on the crossing number of a graph G (i.e. the minimum number of crossing pairs of ...