Counting plane graphs
作者： Micha Sharir , Adam Sheffer , Emo Welzl
关键词: Point set 、 Discrete mathematics 、 Upper and lower bounds 、 Mathematics 、 Combinatorics 、 Linear algebra 、 Hamiltonian (quantum mechanics)
摘要: We derive improved upper bounds on the number of crossing-free straight-edge spanning cycles (also known as Hamiltonian tours and simple polygonizations) that can be embedded over any specific set N points in plane. More specifically, we bound ratio between (or perfect matchings) a point triangulations it. The respective are O(1.8181N) for O(1.1067N) matchings. These imply new O(54.543N) plane (improving upon previous best O(68.664N)). Our analysis is based weighted variant Kasteleyn's linear algebra technique.
acm.org
sci-hub.se 参考文章(20)
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
Marc Noy, Ferran Hurtado, Counting triangulations of almost-convex polygons. Ars Combinatoria. ,vol. 45, ,(1997)
Roger A Horn, Topics in Matrix Analysis ,(2010)
P.W. Kasteleyn, The statistics of dimers on a lattice Physica. ,vol. 27, pp. 1209- 1225 ,(1961) , 10.1016/0031-8914(61)90063-5
Michael Hoffmann, Micha Sharir, Adam Sheffer, Csaba D. Tóth, Emo Welzl, Counting plane graphs: flippability and its applications workshop on algorithms and data structures. pp. 524- 535 ,(2011) , 10.1007/978-3-642-22300-6_44
Kiyoshi Hosono, Note: On convex decompositions of a planar point set Discrete Mathematics. ,vol. 309, pp. 1714- 1717 ,(2009) , 10.1016/J.DISC.2008.02.008
Birgit Vogtenhuber, Oswin Aichholzer, Thomas Hackl, Clemens Huemer, Ferran Hurtado, Hannes Krasser, On the Number of Plane Geometric Graphs Graphs and Combinatorics. ,vol. 23, pp. 67- 84 ,(2007) , 10.1007/S00373-007-0704-5
Naoki Katoh, Shin-ichi Tanigawa, Fast enumeration algorithms for non-crossing geometric graphs Proceedings of the twenty-fourth annual symposium on Computational geometry - SCG '08. ,vol. 42, pp. 328- 337 ,(2008) , 10.1145/1377676.1377733
Micha Sharir, Adam Sheffer, Emo Welzl, On degrees in random triangulations of point sets Journal of Combinatorial Theory, Series A. ,vol. 118, pp. 1979- 1999 ,(2011) , 10.1016/J.JCTA.2011.04.002
F. Hurtado, M. Noy, J. Urrutia, Flipping edges in triangulations Discrete and Computational Geometry. ,vol. 22, pp. 333- 346 ,(1999) , 10.1007/PL00009464