On the number of plane graphs
作者： Clemens Huemer , Birgit Vogtenhuber , Hannes Krasser , Thomas Hackl , Oswin Aichholzer
关键词:
摘要: We investigate the number of plane geometric, i.e., straight-line, graphs, a set S n points in admits. show that graphs and connected as well cycle-free is minimized when convex position. Moreover, these results hold for all with an arbitrary but fixed edges. Consequently, we provide simple proofs spanning trees, (forests), perfect matchings, paths also point sets position.In addition construct new extremal configuration, so-called double zig-zag chain. Most noteworthy this example bears Θ*(√72n) = Θ*(8.4853n) triangulations Θ*(41.1889n) (omitting polynomial factors both cases), improving previously known best maximizing examples.
core.ac.uk
acm.org
elsevier.com
sci-hub.st 参考文章(20)
Oswin Aichholzer, David Orden, Francisco Santos, Bettina Speckmann, On the number of pseudo-triangulations of certain point sets Journal of Combinatorial Theory, Series A. ,vol. 115, pp. 254- 278 ,(2008) , 10.1016/J.JCTA.2007.06.002
Neil J. A. Sloane, The On-Line Encyclopedia of Integer Sequences Calculemus '07 / MKM '07 Proceedings of the 14th symposium on Towards Mechanized Mathematical Assistants: 6th International Conference. pp. 130- 130 ,(2007) , 10.1007/978-3-540-73086-6_12
Handbook of discrete and computational geometry Handbook of discrete and computational geometry. pp. 961- 961 ,(1997) , 10.1201/9781420035315
Philippe Flajolet, Marc Noy, Analytic combinatorics of non-crossing configurations Discrete Mathematics. ,vol. 204, pp. 203- 229 ,(1999) , 10.1016/S0012-365X(98)00372-0
Oswin Aichholzer, Ferran Hurtado, Marc Noy, A lower bound on the number of triangulations of planar point sets Computational Geometry: Theory and Applications. ,vol. 29, pp. 135- 145 ,(2004) , 10.1016/J.COMGEO.2004.02.003
Alfredo Garcı́a, Marc Noy, Javier Tejel, Lower bounds on the number of crossing-free subgraphs of K N Computational Geometry: Theory and Applications. ,vol. 16, pp. 211- 221 ,(2000) , 10.1016/S0925-7721(00)00010-9
Oswin Aichholzer, Franz Aurenhammer, Hannes Krasser, Bettina Speckmann, Convexity minimizes pseudo-triangulations canadian conference on computational geometry. ,vol. 28, pp. 3- 10 ,(2004) , 10.1016/J.COMGEO.2004.01.002
Oswin Aichholzer, Hannes Krasser, Abstract order type extension and new results on the rectilinear crossing number european workshop on computational geometry. ,vol. 36, pp. 2- 15 ,(2007) , 10.1016/J.COMGEO.2005.07.005
Paul Erdös, Richard K Guy, Crossing Number Problems American Mathematical Monthly. ,vol. 80, pp. 52- 58 ,(1973) , 10.1080/00029890.1973.11993230
M. Ajtai, V. Chvátal, M.M. Newborn, E. Szemerédi, Crossing-Free Subgraphs Theory and Practice of Combinatorics - A collection of articles honoring Anton Kotzig on the occasion of his sixtieth birthday. ,vol. 60, pp. 9- 12 ,(1982) , 10.1016/S0304-0208(08)73484-4