skip to main content
column

Computational geometry column 54

Published: 19 December 2012 Publication History

Abstract

This column is devoted to non-crossing configurations in the plane realized with straight line segments connecting pairs of points from a finite ground set. Graph classes of interest realized in this way include matchings, spanning trees, spanning cycles, and triangulations. We review some problems and results in this area. At the end we list some open problems.

References

[1]
M. Abellanas, A. García, F. Hurtado, and J. Tejel, Caminos alternantes, X Encuentros de Geometrá Computacional (in Spanish), Sevilla, 2003, pp. 7--12.
[2]
O. Aichholzer, T. Hackl, B. Vogtenhuber, C. Huemer, F. Hurtado and H. Krasser, On the number of plane geometric graphs, Graphs and Combinatorics 23(1) (2007), 67--84.
[3]
M. Ajtai, V. Chvátal, M. Newborn and E. Szemerédi, Crossing-free subgraphs, Annals of Discrete Mathematics 12 (1982), 9--12.
[4]
G. Araujo, A. Dumitrescu, F. Hurtado, M. Noy and J. Urrutia, On the chromatic number of some geometric type Kneser graphs, Computational Geometry: Theory and Applications 32 (2005), 59--69.
[5]
E. M. Arkin, J. S. B. Mitchell and C. D. Piatko, Minimum-link watchman tours, Information Processing Letters 86 (2003), 203--207.
[6]
N. Alon, S. Rajagopalan and S. Suri: Long non-crossing configurations in the plane, Fundamenta Informaticae 22 (1995), 385--394.
[7]
S. Avital and H. Hanani, Graphs (in Hebrew), Gilyonot Lematematika 3 (1966), 2--8.
[8]
P. Brass, G. Károlyi, P. Valtr, A Turán-type extremal theory of convex geometric graphs, in: Discrete and Computational Geometry, vol. 25 of Algorithms Combin., Springer, Berlin, 2003, pp. 275--300.
[9]
K. Buchin, C. Knauer, K. Kriegel, A. Schulz, and R. Seidel, On the number of cycles in planar graphs, Proc. 13th Annual International Conference on Computing and Combinatorics, vol. 4598 of LNCS, Springer, 2007, pp. 97--107.
[10]
J. černý, Z. Dvořák, V. Jelínek, and J. Kára, Noncrossing Hamiltonian paths in geometric graphs, Discrete Applied Mathematics 155 (2007), 1096--1105.
[11]
E. Demaine, Simple polygonizations, http://erikdemaine.org/polygonization/ (version of October, 2012).
[12]
E.D. Demaine and J. O'Rourke, Open problems from CCCG 2010, in Proc. 23rd Canadian Conference on Computational Geometry, 2011, Toronto, ON, pp. 153--156.
[13]
A. Dumitrescu, On two lower bound constructions, Proc. 11th Canadian Conference on Computational Geometry, 1999, pp. 111--114.
[14]
A. Dumitrescu, On the maximum multiplicity of some extreme geometric configurations in the plane, Geombinatorics 12(1) (2002), 5--14.
[15]
A. Dumitrescu, A. Schulz, A. Sheffer and Cs. D. Tóth, Bounds on the maximum multiplicity of some common geometric graphs, Proc. 28th Symposium on Theoretical Aspects of Computer Science, vol. 9 of Leibniz International Proceedings in Informatics (LIPIcs), 2011, pp. 637--648.
[16]
A. Dumitrescu and C. D. Tóth, Long non-crossing configurations in the plane, Discrete and Computational Geometry 44(4) (2010), 727--752.
[17]
A. Dumitrescu and Cs. D. Tóth, Covering paths for planar point sets, Proc. 20th International Symposium on Graph Drawing (GD 2012), LNCS, Springer, to appear.
[18]
D. Eppstein: Spanning trees and spanners, in J.-R. Sack and J. Urrutia (editors), Handbook of Computational Geometry, pages 425--461, Elsevier Science, Amsterdam, 2000.
[19]
P. Erdös and G. Szekeres, A combinatorial problem in geometry, Compositio Mathematica 2 (1935), 463--470.
[20]
A. P. Figueroa, A note on a theorem of Perles concerning non-crossing paths in convex geometric graphs, Computational Geometry: Theory and Applications 42 (2009) 90--91.
[21]
A. García, M. Noy and A. Tejel, Lower bounds on the number of crossing-free subgraphs of KN, Computational Geometry: Theory and Applications 16(4) (2000), 211--221.
[22]
D. Gerbner and B. Keszegh, Non-crossing covering paths for planar point sets, manuscript, September 2012.
[23]
P. Gritzmann, B. Mohar, J. Pach, and R. Pollack, Embedding a planar triangulation with vertices at specified points, American Mathematical Monthly 98 (1991), 165--166.
[24]
M. Hoffmann, M. Sharir, A. Schulz, A. Sheffer, Cs. D. Tóth, and E. Welzl, Counting plane graphs: flippability and its applications, Thirty Essays on Geometric Graph Theory (J. Pach, ed.), vol. 29 of Algorithms and Combinatorics, Springer, 2012, to appear. Also at arxiv.org/abs/1012.0591.
[25]
G. Károlyi, J. Pach, and G. Tóth, Ramsey-type results for geometric graphs, I, Discrete & Computational Geometry 18(3) (1997), 247--255.
[26]
G. Károlyi, J. Pach, G. Tóth, and P. Valtr, Ramsey-type results for geometric graphs, II, Discrete & Computational Geometry 20(3) (1998), 375--388.
[27]
E. Kranakis, D. Krizanc and L. Meertens, Link length of rectilinear Hamiltonian tours in grids, Ars Combinatoria 38 (1994), 177--192.
[28]
M. van Kreveld, M. Löffler, and J. Pach, How many potatoes are in a mesh? Proc. 23rd International Symposium on. Algorithms and Computation (ISAAC 2012), LNCS, Springer, 2012, to appear. Also at arxiv.org/abs/1209.3954.
[29]
Y. Kupitz, Extremal problems in combinatorial geometry, Aarhus University Lecture Notes Series, 53 (1979), Aarhus University, Denmark.
[30]
J. Kyncl, J. Pach, and G. Tóth, Long alternating paths in bicolored point sets, Discrete Mathematics 308(19) (2008), 4315--4321.
[31]
C. Merino, G. Salazar, and J. Urrutia, On the length of the longest alternating paths for multicolored point set, Discrete Mathematics 306 (2006) 1791--1797.
[32]
J. S. B. Mitchell: Geometric shortest paths and network optimization, in J.-R. Sack and J. Urrutia (editors), Handbook of Computational Geometry, pp. 633--701, Elsevier, Amsterdam, 2000.
[33]
M. Newborn and W. O. J. Moser, Optimal crossing-free Hamiltonian circuit drawings of Kn, Journal of Combinatorial Theory Ser. B 29 (1980), 13--26.
[34]
A. Razen, J. Snoeyink, and E. Welzl, Number of crossing-free geometric graphs vs. triangulations, Electronic Notes in Discrete Mathematics 31 (2008), 195--200.
[35]
F. Santos and R. Seidel, A better upper bound on the number of triangulations of a planar point set, Journal of Combinatorial Theory Ser. A 102(1) (2003), 186--193.
[36]
M. Sharir and A. Sheffer, Counting triangulations of planar point sets, Electronic Journal of Combinatorics 18 (2011), P70.
[37]
M. Sharir and A. Sheffer, Counting plane graphs: cross-graph charging schemes, Proc. 20th International Symposium on Graph Drawing (GD 2012), LNCS, Springer, to appear.
[38]
M. Sharir, A. Sheffer, and E.Welzl, Counting plane graphs: perfect matchings, spanning cycles, and Kasteleyn's technique, Proc. 28th ACM Symp. on Computational Geometry (2012), 189--198.
[39]
M. Sharir and E. Welzl, On the number of crossing-free matchings, cycles, and partitions, SIAM Journal on Computing 36(3) (2006), 695--720.
[40]
M. Sharir and E. Welzl, Random triangulations of planar point sets, Proc. 22nd Annual ACMSIAM Symposium on Computational Geometry, ACM Press, 2006, pp. 273--281.
[41]
A. Sheffer, Numbers of plane graphs, http://www.cs.tau.ac.il/~sheffera/counting/PlaneGraphs.html (version of October, 2012).
[42]
G. Tóth, Note on geometric graphs, Journal of Combinatorial Theory, Ser. A 89 (2000), 126--132.

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM SIGACT News
ACM SIGACT News  Volume 43, Issue 4
December 2012
120 pages
ISSN:0163-5700
DOI:10.1145/2421119
Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 December 2012
Published in SIGACT Volume 43, Issue 4

Check for updates

Author Tags

  1. Hamiltonian cycle
  2. geometric graph
  3. non-crossing property
  4. perfect matching
  5. spanning tree
  6. triangulation

Qualifiers

  • Column

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 30 Jan 2025

Other Metrics

Citations

Cited By

View all

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media