License: 
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2011.637
URN: urn:nbn:de:0030-drops-30505
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2011/3050/
Dumitrescu, Adrian ;
Schulz, Andre ;
Sheffer, Adam ;
Toth, Csaba D.
Bounds on the maximum multiplicity of some common geometric graphs
Abstract
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 previous best construction, the double zig-zag chain studied by Aichholzer et al.
(ii) We present a new lower bound of Omega(11.97^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.664^n) non-crossing spanning cycles.
(iv) We derive exponential lower bounds for the number of maximum and minimum weighted geometric graphs (matchings, spanning trees, and tours). It was known that the number of longest non-crossing spanning trees of a point set can be exponentially large, and here we show that this can be also realized with points in convex position. 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(n log n) time algorithm for computing them.
BibTeX - Entry
@InProceedings{dumitrescu_et_al:LIPIcs:2011:3050,
author = {Adrian Dumitrescu and Andre Schulz and Adam Sheffer and Csaba D. Toth},
title = {{Bounds on the maximum multiplicity of some common geometric graphs}},
booktitle = {28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011) },
pages = {637--648},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-25-5},
ISSN = {1868-8969},
year = {2011},
volume = {9},
editor = {Thomas Schwentick and Christoph D{\"u}rr},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2011/3050},
URN = {urn:nbn:de:0030-drops-30505},
doi = {10.4230/LIPIcs.STACS.2011.637},
annote = {Keywords: combinatorial geometry, matching, triangulation, spanning tree, spanning cycle, weighted structure, non-crossing condition}
}
|
Keywords: |
|
combinatorial geometry, matching, triangulation, spanning tree, spanning cycle, weighted structure, non-crossing condition |
|
Collection: |
|
28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011) |
|
Issue Date: |
|
2011 |
|
Date of publication: |
|
11.03.2011 |
