{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:21:21Z","timestamp":1750306881408,"version":"3.41.0"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2012,12,19]],"date-time":"2012-12-19T00:00:00Z","timestamp":1355875200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGACT News"],"published-print":{"date-parts":[[2012,12,19]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/2421119.2421136","type":"journal-article","created":{"date-parts":[[2013,1,2]],"date-time":"2013-01-02T13:23:15Z","timestamp":1357132995000},"page":"90-97","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Computational geometry column 54"],"prefix":"10.1145","volume":"43","author":[{"given":"Adrian","family":"Dumitrescu","sequence":"first","affiliation":[{"name":"University of Wisconsin--Milwaukee, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Csaba D.","family":"T\u00f3th","sequence":"additional","affiliation":[{"name":"University of Calgary, Canada and Tufts University, Medford, MA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,12,19]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"7","article-title":"Caminos alternantes, X Encuentros de Geometr\u00e1 Computacional (in Spanish)","author":"Abellanas M.","year":"2003","unstructured":"M. Abellanas , A. Garc\u00eda , F. Hurtado , and J. Tejel , Caminos alternantes, X Encuentros de Geometr\u00e1 Computacional (in Spanish) , Sevilla , 2003 , pp. 7 -- 12 . M. Abellanas, A. Garc\u00eda, F. Hurtado, and J. Tejel, Caminos alternantes, X Encuentros de Geometr\u00e1 Computacional (in Spanish), Sevilla, 2003, pp. 7--12.","journal-title":"Sevilla"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-007-0704-5"},{"key":"e_1_2_1_3_1","first-page":"9","article-title":"Crossing-free subgraphs","volume":"12","author":"Ajtai M.","year":"1982","unstructured":"M. Ajtai , V. Chv\u00e1tal , M. Newborn and E. Szemer\u00e9di , Crossing-free subgraphs , Annals of Discrete Mathematics 12 ( 1982 ), 9 -- 12 . M. Ajtai, V. Chv\u00e1tal, M. Newborn and E. Szemer\u00e9di, Crossing-free subgraphs, Annals of Discrete Mathematics 12 (1982), 9--12.","journal-title":"Annals of Discrete Mathematics"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2004.10.003"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(02)00502-1"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/2383356.2383361"},{"key":"e_1_2_1_7_1","first-page":"2","article-title":"Graphs (in Hebrew)","volume":"3","author":"Avital S.","year":"1966","unstructured":"S. Avital and H. Hanani , Graphs (in Hebrew) , Gilyonot Lematematika 3 ( 1966 ), 2 -- 8 . S. Avital and H. Hanani, Graphs (in Hebrew), Gilyonot Lematematika 3 (1966), 2--8.","journal-title":"Gilyonot Lematematika"},{"key":"e_1_2_1_8_1","series-title":"Algorithms Combin","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1007\/978-3-642-55566-4_12","volume-title":"Discrete and Computational Geometry","author":"Brass P.","year":"2003","unstructured":"P. Brass , G. K\u00e1rolyi , P. Valtr , A Tur\u00e1n-type extremal theory of convex geometric graphs , in: Discrete and Computational Geometry , vol. 25 of Algorithms Combin ., Springer , Berlin , 2003 , pp. 275 -- 300 . P. Brass, G. K\u00e1rolyi, P. Valtr, A Tur\u00e1n-type extremal theory of convex geometric graphs, in: Discrete and Computational Geometry, vol. 25 of Algorithms Combin., Springer, Berlin, 2003, pp. 275--300."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/2394650.2394662"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2005.12.010"},{"key":"e_1_2_1_11_1","unstructured":"E. Demaine Simple polygonizations http:\/\/erikdemaine.org\/polygonization\/ (version of October 2012).  E. Demaine Simple polygonizations http:\/\/erikdemaine.org\/polygonization\/ (version of October 2012)."},{"key":"e_1_2_1_12_1","first-page":"153","volume-title":"Proc. 23rd Canadian Conference on Computational Geometry","author":"Demaine E.D.","year":"2011","unstructured":"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 . 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."},{"key":"e_1_2_1_13_1","first-page":"111","volume-title":"Proc. 11th Canadian Conference on Computational Geometry","author":"Dumitrescu A.","year":"1999","unstructured":"A. Dumitrescu , On two lower bound constructions , Proc. 11th Canadian Conference on Computational Geometry , 1999 , pp. 111 -- 114 . A. Dumitrescu, On two lower bound constructions, Proc. 11th Canadian Conference on Computational Geometry, 1999, pp. 111--114."},{"issue":"1","key":"e_1_2_1_14_1","first-page":"5","article-title":"On the maximum multiplicity of some extreme geometric configurations in the plane","volume":"12","author":"Dumitrescu A.","year":"2002","unstructured":"A. Dumitrescu , On the maximum multiplicity of some extreme geometric configurations in the plane , Geombinatorics 12 ( 1 ) ( 2002 ), 5 -- 14 . A. Dumitrescu, On the maximum multiplicity of some extreme geometric configurations in the plane, Geombinatorics 12(1) (2002), 5--14.","journal-title":"Geombinatorics"},{"key":"e_1_2_1_15_1","first-page":"637","volume-title":"Proc. 28th Symposium on Theoretical Aspects of Computer Science, vol. 9 of Leibniz International Proceedings in Informatics (LIPIcs)","author":"Dumitrescu A.","year":"2011","unstructured":"A. Dumitrescu , A. Schulz , A. Sheffer and Cs. D. T\u00f3th, 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 . A. Dumitrescu, A. Schulz, A. Sheffer and Cs. D. T\u00f3th, 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."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-010-9277-9"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36763-2_27"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-044482537-7\/50010-3"},{"key":"e_1_2_1_19_1","first-page":"463","article-title":"A combinatorial problem in geometry","volume":"2","author":"Erd\u00f6s P.","year":"1935","unstructured":"P. Erd\u00f6s and G. Szekeres , A combinatorial problem in geometry , Compositio Mathematica 2 ( 1935 ), 463 -- 470 . P. Erd\u00f6s and G. Szekeres, A combinatorial problem in geometry, Compositio Mathematica 2 (1935), 463--470.","journal-title":"Compositio Mathematica"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2008.07.002"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(00)00010-9"},{"key":"e_1_2_1_22_1","volume-title":"September","author":"Gerbner D.","year":"2012","unstructured":"D. Gerbner and B. Keszegh , Non-crossing covering paths for planar point sets, manuscript , September 2012 . D. Gerbner and B. Keszegh, Non-crossing covering paths for planar point sets, manuscript, September 2012."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.2307\/2323956"},{"key":"e_1_2_1_24_1","series-title":"Algorithms and Combinatorics","volume-title":"Thirty Essays on Geometric Graph Theory","author":"Hoffmann M.","year":"2012","unstructured":"M. Hoffmann , M. Sharir , A. Schulz , A. Sheffer , Cs. D. T\u00f3th , 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. M. Hoffmann, M. Sharir, A. Schulz, A. Sheffer, Cs. D. T\u00f3th, 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."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009317"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009391"},{"key":"e_1_2_1_27_1","first-page":"177","article-title":"Link length of rectilinear Hamiltonian tours in grids","volume":"38","author":"Kranakis E.","year":"1994","unstructured":"E. Kranakis , D. Krizanc and L. Meertens , Link length of rectilinear Hamiltonian tours in grids , Ars Combinatoria 38 ( 1994 ), 177 -- 192 . E. Kranakis, D. Krizanc and L. Meertens, Link length of rectilinear Hamiltonian tours in grids, Ars Combinatoria 38 (1994), 177--192.","journal-title":"Ars Combinatoria"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-35261-4_20"},{"key":"e_1_2_1_29_1","volume-title":"Extremal problems in combinatorial geometry","author":"Kupitz Y.","year":"1979","unstructured":"Y. Kupitz , Extremal problems in combinatorial geometry , Aarhus University Lecture Notes Series, 53 ( 1979 ), Aarhus University , Denmark. Y. Kupitz, Extremal problems in combinatorial geometry, Aarhus University Lecture Notes Series, 53 (1979), Aarhus University, Denmark."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2007.08.013"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2006.03.035"},{"key":"e_1_2_1_32_1","first-page":"633","volume-title":"J.-R","author":"Mitchell J. S. B.","year":"2000","unstructured":"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 . 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."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(80)90041-6"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.endm.2008.06.039"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0097-3165(03)00002-5"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.37236\/557"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36763-2_3"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2261250.2261277"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/050636036"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1137856.1137898"},{"key":"e_1_2_1_41_1","unstructured":"A. Sheffer Numbers of plane graphs http:\/\/www.cs.tau.ac.il\/~sheffera\/counting\/PlaneGraphs.html (version of October 2012).  A. Sheffer Numbers of plane graphs http:\/\/www.cs.tau.ac.il\/~sheffera\/counting\/PlaneGraphs.html (version of October 2012)."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcta.1999.3001"}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2421119.2421136","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2421119.2421136","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:18:34Z","timestamp":1750234714000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2421119.2421136"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,12,19]]},"references-count":42,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2012,12,19]]}},"alternative-id":["10.1145\/2421119.2421136"],"URL":"https:\/\/doi.org\/10.1145\/2421119.2421136","relation":{},"ISSN":["0163-5700"],"issn-type":[{"type":"print","value":"0163-5700"}],"subject":[],"published":{"date-parts":[[2012,12,19]]},"assertion":[{"value":"2012-12-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}