{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,29]],"date-time":"2026-09-29T05:43:28Z","timestamp":1790660608259,"version":"4.1.0"},"reference-count":58,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"8","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>We provide linear-time algorithms for geometric graphs with sublinearly many edge crossings. That is, we provide algorithms running in $O(n)$ time on connected geometric graphs having n vertices and k pairwise crossings, where k is smaller than n by an iterated logarithmic factor. Specific problems that we study include Voronoi diagrams and single-source shortest paths. Our algorithms all run in linear time in the standard comparison-based computational model; hence, we make no assumptions about the distribution or bit complexities of edge weights, nor do we utilize unusual bit-level operations on memory words. Instead, our algorithms are based on a planarization method that \u201czeros in\u201d on edge crossings, together with methods for applying planar separator decompositions to geometric graphs with sublinearly many crossings. Incidentally, our planarization algorithm also solves an open computational geometry problem of Chazelle for triangulating a self-intersecting polygonal chain having n segments and k crossings in linear time, for the case when k is sublinear in n by an iterated logarithmic factor.<\/jats:p>","DOI":"10.1137\/090759112","type":"journal-article","created":{"date-parts":[[2010,12,14]],"date-time":"2010-12-14T18:48:48Z","timestamp":1292352528000},"page":"3814-3829","source":"Crossref","is-referenced-by-count":8,"title":["Linear-Time Algorithms for Geometric Graphs with Sublinearly Many Edge Crossings"],"prefix":"10.1137","volume":"39","author":[{"given":"David","family":"Eppstein","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael T.","family":"Goodrich","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Darren","family":"Strash","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2010,12,14]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"P. K. Agarwal,\n                      Geometric partitioning and its applications\n                      , in Computational Geometry: Papers from the DIMACS Special Year, J. E. Goodman, R. Pollack, and W. Steiger, eds., AMS, Providence, RI, 1991, pp. 1\u201338.","DOI":"10.1090\/dimacs\/006\/01"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01759076"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"D. Armon and J. Reif,\n                      A dynamic separator algorithm\n                      , in Proceedings of the 3rd Workshop on Algorithms and Data Structures, Lecture Notes Comput. Sci. 709, Springer-Verlag, New York, Berlin, 1993, pp. 107\u2013118.","DOI":"10.1007\/3-540-57155-8_240"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1145\/116873.116880"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"F. Aurenhammer and R. Klein,\n                      Voronoi diagrams\n                      , in Handbook of Computational Geometry, J.R. Sack and J. Urrutia, eds., Elsevier Science Publishers\/North\u2013Holland, Amsterdam, 2000, pp. 201\u2013290.","DOI":"10.1016\/B978-044482537-7\/50006-1"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1979.1675432"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1007\/BF02293035"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574703"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1145\/355541.355562"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1145\/147508.147511"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840440"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1137\/0205051"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195992000287"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195992000081"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187740"},{"key":"R16","unstructured":"T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein,\n                      Introduction to Algorithms\n                      , 2nd ed., MIT Press, Cambridge, MA, 2001."},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195995000210"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"F. Dehne, X. Deng, P. Dymond, A. Fabri, and A. A. Khokhar,\n                      A randomized parallel\n                      3\n                      d convex hull algorithm for coarse grained multicomputers\n                      , in Proceedings of the Seventh Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA '95), New York, 1995, ACM, New York, pp. 27\u201333.","DOI":"10.1145\/215399.215410"},{"key":"R19","unstructured":"X. Deng and B. Zhu,\n                      A randomized algorithm for Voronoi diagram of line segments on coarse grained multiprocessors\n                      , in Parallel Processing Symposium, 1996, Proceedings of the 10th International Parallel Processing Symposium, Honolulu, HI, 1996, IEEE Computer Society Press, Piscataway, NJ, pp. 192\u2013198."},{"key":"R20","unstructured":"G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis,\n                      Graph Drawing\n                      , Prentice\u2013Hall, Upper Saddle River, NJ, 1999."},{"key":"R21","unstructured":"H. Edelsbrunner, J. W. Jaromczyk, J. W. Penny, and G. \u015awi\u0105tek,\n                      Primal canoes: Optimal arrangements of segments\n                      , in Proceedings of the 3rd Canadian Conference on Computational Geometry, Burnaby, BC, 1991, pp. 224\u2013227."},{"key":"R22","doi-asserted-by":"crossref","unstructured":"D. Eppstein,\n                      Spanning trees and spanners\n                      , in Handbook of Computational Geometry, J.R. Sack and J. Urrutia, eds., Elsevier, New York, 2000, pp. 425\u2013461.","DOI":"10.1016\/B978-044482537-7\/50010-3"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700370084"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0002"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"D. Eppstein and M. T. Goodrich,\n                      Studying (non-planar) road networks through an algorithmic lens\n                      , in Proceedings of the 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (GIS '08), New York, 2008, ACM, New York, pp. 1\u201310.","DOI":"10.1145\/1463434.1463455"},{"key":"R26","doi-asserted-by":"crossref","unstructured":"D. Eppstein, M. T. Goodrich, and D. Strash,\n                      Linear-time algorithms for geometric graphs with sublinearly many crossings\n                      , in Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '09), New York, 2009, SIAM, Philadelphia, pp. 150\u2013159.","DOI":"10.1137\/1.9781611973068.18"},{"key":"R27","doi-asserted-by":"crossref","unstructured":"D. Eppstein, G. L. Miller, and S.H. Teng,\n                      A deterministic linear time algorithm for geometric separators and its applications\n                      , in Proceedings of the 9th Annual ACM Symposium on Computational Geometry, San Diego, CA, 1993, ACM, New York, pp. 99\u2013108.","DOI":"10.1145\/160985.161005"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1002\/1097-0037(200010)36:3<156::AID-NET2>3.0.CO;2-L"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1103\/RevModPhys.42.271"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28874"},{"key":"R31","unstructured":"A. V. Goldberg,\n                      Scaling algorithms for the shortest paths problem\n                      , in Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '93), Austin, TX, 1993, SIAM, Philadelphia, pp. 222\u2013231."},{"key":"R32","unstructured":"A. V. Goldberg and C. Harrelson,\n                      Computing the shortest path: $A^*$ search meets graph theory\n                      , in Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '05), Vancouver, BC, 2005, SIAM, Philadelphia, pp. 156\u2013165."},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1076"},{"key":"R34","unstructured":"M. T. Goodrich and R. Tamassia,\n                      Algorithm Design: Foundations, Analysis, and Internet Examples\n                      , John Wiley & Sons, New York, 2002."},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(83)90013-5"},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799350232"},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1493"},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1145\/1064546.1180616"},{"key":"R39","doi-asserted-by":"publisher","DOI":"10.1145\/201019.201022"},{"key":"R40","doi-asserted-by":"publisher","DOI":"10.1002\/net.20131"},{"key":"R41","doi-asserted-by":"publisher","DOI":"10.1007\/BF00993195"},{"key":"R42","doi-asserted-by":"publisher","DOI":"10.1137\/0136016"},{"key":"R43","first-page":"315","volume":"40","author":"Mare\u0161 M.","year":"2004","journal-title":"Arch. Math. (Brno)"},{"key":"R44","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90066-X"},{"key":"R45","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00046-4"},{"key":"R46","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(86)90030-9"},{"key":"R47","doi-asserted-by":"publisher","DOI":"10.1145\/256292.256294"},{"key":"R48","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827594262613"},{"key":"R49","doi-asserted-by":"crossref","unstructured":"B. Mohar and C. Thomassen,\n                      Graphs on Surfaces\n                      , Johns Hopkins University Press, Baltimore, 2001.","DOI":"10.56021\/9780801866890"},{"key":"R50","doi-asserted-by":"crossref","unstructured":"J. Pach,\n                      Towards a Theory of Geometric Graphs\n                      , Contemp. Math. 342, AMS, Providence, RI, 2004.","DOI":"10.1090\/conm\/342"},{"key":"R51","doi-asserted-by":"publisher","DOI":"10.1145\/261342.261352"},{"key":"R52","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-001-0029-8"},{"key":"R53","doi-asserted-by":"crossref","unstructured":"P. Sanders and D. Schultes,\n                      Highway hierarchies hasten exact shortest path queries\n                      , in Proceedings of the 17th European Symposium on Algorithms (ESA), Lecture Notes in Comput. Sci. 3669, Springer, New York, 2005, pp. 568\u2013579.","DOI":"10.1007\/11561071_51"},{"key":"R54","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840435"},{"key":"R55","doi-asserted-by":"crossref","unstructured":"D. A. Spielman and S.H. Teng,\n                      Disk packings and planar separators\n                      , in Proceedings of the 12th Annual ACM Symposium on Computational Geometry, ACM, New York, 1996, pp. 349\u2013358.","DOI":"10.1145\/237218.237404"},{"key":"R56","doi-asserted-by":"publisher","DOI":"10.1145\/316542.316548"},{"key":"R57","doi-asserted-by":"crossref","unstructured":"W. T. Trotter,\n                      Planar Graphs\n                      , DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 9, AMS, Providence, RI, 1993.","DOI":"10.1090\/dimacs\/009"},{"key":"R58","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.32.1.65"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/090759112","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:34:23Z","timestamp":1787337263000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/090759112"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1]]},"references-count":58,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["10.1137\/090759112"],"URL":"https:\/\/doi.org\/10.1137\/090759112","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1]]}}}