Bounds on the maximum multiplicity of some common geometric graphs

Details Bounds on the maximum multiplicity of some common geometric graphs Bounds on the maximum multiplicity of some common geometric graphs

2010-12-27

arxiv.org/abs/1012.5664v2

Computer Science

Discrete Mathematics

Scientific paper

We obtain new lower and upper bounds for the maximum multiplicity of some weighted and, respectively, non-weighted common geometric graphs drawn on n points in the plane in general position (with no three points collinear): perfect matchings, spanning trees, spanning cycles (tours), and triangulations. (i) We present a new lower bound construction for the maximum number of triangulations a set of n points in general position can have. In particular, we show that a generalized double chain formed by two almost convex chains admits {\Omega}(8.65^n) different triangulations. This improves the bound {\Omega}(8.48^n) achieved by the double zig-zag chain configuration studied by Aichholzer et al. (ii) We present a new lower bound of {\Omega}(12.00^n) for the number of non-crossing spanning trees of the double chain composed of two convex chains. The previous bound, {\Omega}(10.42^n), stood unchanged for more than 10 years. (iii) Using a recent upper bound of 30^n for the number of triangulations, due to Sharir and Sheffer, we show that n points in the plane in general position admit at most O(68.62^n) non-crossing spanning cycles. (iv) We derive lower bounds for the number of maximum and minimum weighted geometric graphs (matchings, spanning trees, and tours). We show that the number of shortest non-crossing tours can be exponential in n. Likewise, we show that both the number of longest non-crossing tours and the number of longest non-crossing perfect matchings can be exponential in n. Moreover, we show that there are sets of n points in convex position with an exponential number of longest non-crossing spanning trees. For points in convex position we obtain tight bounds for the number of longest and shortest tours. We give a combinatorial characterization of the longest tours, which leads to an O(nlog n) time algorithm for computing them.

Affiliated with

Also associated with

No associations

Rating

Bounds on the maximum multiplicity of some common geometric graphs 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 Bounds on the maximum multiplicity of some common geometric graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bounds on the maximum multiplicity of some common geometric graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-427536