{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T01:59:00Z","timestamp":1743127140619,"version":"3.40.3"},"publisher-location":"Cham","reference-count":25,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031630200"},{"type":"electronic","value":"9783031630217"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024]]},"DOI":"10.1007\/978-3-031-63021-7_39","type":"book-chapter","created":{"date-parts":[[2024,6,21]],"date-time":"2024-06-21T13:02:29Z","timestamp":1718974949000},"page":"509-522","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Efficient Computation of\u00a0Crossing Components and\u00a0Shortcut Hulls"],"prefix":"10.1007","author":[{"given":"Nikolas Alexander","family":"Schwarz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sabine","family":"Storandt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,6,22]]},"reference":[{"key":"39_CR1","doi-asserted-by":"publisher","unstructured":"Ackerman, E.: On topological graphs with at most four crossings per edge. Comput. Geom. 85, 101574 (2019). https:\/\/doi.org\/10.1016\/j.comgeo.2019.101574. https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0925772119301154","DOI":"10.1016\/j.comgeo.2019.101574"},{"issue":"5","key":"39_CR2","doi-asserted-by":"publisher","first-page":"864","DOI":"10.1109\/TRO.2005.851359","volume":"21","author":"C Belta","year":"2005","unstructured":"Belta, C., Isler, V., Pappas, G.J.: Discrete abstractions for robot motion planning and control in polygonal environments. IEEE Trans. Rob. 21(5), 864\u2013874 (2005)","journal-title":"IEEE Trans. Rob."},{"key":"39_CR3","doi-asserted-by":"publisher","unstructured":"Bentley, Ottmann: Algorithms for reporting and counting geometric intersections. IEEE Trans. Comput. C-28(9), 643\u2013647 (1979). https:\/\/doi.org\/10.1109\/TC.1979.1675432","DOI":"10.1109\/TC.1979.1675432"},{"key":"39_CR4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2","volume-title":"Computational Geometry: Algorithms and Applications","author":"M de Berg","year":"2008","unstructured":"de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational Geometry: Algorithms and Applications, 3rd edn. Springer, Germany (2008). https:\/\/doi.org\/10.1007\/978-3-540-77974-2","edition":"3"},{"key":"39_CR5","doi-asserted-by":"publisher","unstructured":"Shortcut hulls: vertex-restricted outer simplifications of polygons. Comput. Geom. 112, 101983 (2023). https:\/\/doi.org\/10.1016\/j.comgeo.2023.101983. https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0925772123000032","DOI":"10.1016\/j.comgeo.2023.101983"},{"key":"39_CR6","unstructured":"Chartrand, G., Harary, F.: Planar permutation graphs. In: Annales de l\u2019institut Henri Poincar\u00e9. Section B. Calcul des probabilit\u00e9s et statistiques, vol.\u00a03, pp. 433\u2013438 (1967)"},{"issue":"1","key":"39_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/147508.147511","volume":"39","author":"B Chazelle","year":"1992","unstructured":"Chazelle, B., Edelsbrunner, H.: An optimal algorithm for intersecting line segments in the plane. J. ACM 39(1), 1\u201354 (1992). https:\/\/doi.org\/10.1145\/147508.147511","journal-title":"J. ACM"},{"issue":"6","key":"39_CR8","doi-asserted-by":"publisher","first-page":"1277","DOI":"10.1109\/TVCG.2008.135","volume":"14","author":"W Cui","year":"2008","unstructured":"Cui, W., Zhou, H., Qu, H., Wong, P.C., Li, X.: Geometry-based edge clustering for graph visualization. IEEE Trans. Vis. Comput. Graph. 14(6), 1277\u20131284 (2008)","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"issue":"06","key":"39_CR9","doi-asserted-by":"publisher","first-page":"543","DOI":"10.1142\/S021819591250015X","volume":"22","author":"HR Dehkordi","year":"2012","unstructured":"Dehkordi, H.R., Eades, P.: Every outer-1-plane graph has a right angle crossing drawing. Int. J. Comput. Geom. Appl. 22(06), 543\u2013557 (2012)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"39_CR10","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/j.tcs.2016.05.017","volume":"639","author":"HR Dehkordi","year":"2016","unstructured":"Dehkordi, H.R., Eades, P., Hong, S.H., Nguyen, Q.: Circular right-angle crossing drawings in linear time. Theor. Comput. Sci. 639, 26\u201341 (2016)","journal-title":"Theor. Comput. Sci."},{"key":"39_CR11","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1007\/BF01187020","volume":"11","author":"P Eades","year":"1994","unstructured":"Eades, P., Wormald, N.C.: Edge crossings in drawings of bipartite graphs. Algorithmica 11, 379\u2013403 (1994)","journal-title":"Algorithmica"},{"issue":"8","key":"39_CR12","doi-asserted-by":"publisher","first-page":"3814","DOI":"10.1137\/090759112","volume":"39","author":"D Eppstein","year":"2010","unstructured":"Eppstein, D., Goodrich, M.T., Strash, D.: Linear-time algorithms for geometric graphs with sublinearly many edge crossings. SIAM J. Comput. 39(8), 3814\u20133829 (2010)","journal-title":"SIAM J. Comput."},{"key":"39_CR13","doi-asserted-by":"publisher","unstructured":"Graham, R.L., Frances Yao, F.: Finding the convex hull of a simple polygon. J. Algorithms 4(4), 324\u2013331 (1983). https:\/\/doi.org\/10.1016\/0196-6774(83)90013-5. https:\/\/www.sciencedirect.com\/science\/article\/pii\/0196677483900135","DOI":"10.1016\/0196-6774(83)90013-5"},{"key":"39_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1007\/3-540-19487-8_7","volume-title":"SWAT 88","author":"L Guibas","year":"1988","unstructured":"Guibas, L., Overmars, M., Sharir, M.: Intersecting line segments, ray shooting, and other applications of geometric partitioning techniques. In: Karlsson, R., Lingas, A. (eds.) SWAT 1988. LNCS, vol. 318, pp. 64\u201373. Springer, Heidelberg (1988). https:\/\/doi.org\/10.1007\/3-540-19487-8_7"},{"issue":"1\u20134","key":"39_CR15","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/BF01553883","volume":"4","author":"J Hershberger","year":"1989","unstructured":"Hershberger, J.: An optimal visibility graph algorithm for triangulated simple polygons. Algorithmica 4(1\u20134), 141\u2013155 (1989). https:\/\/doi.org\/10.1007\/BF01553883","journal-title":"Algorithmica"},{"issue":"2","key":"39_CR16","first-page":"45","volume":"10","author":"F Klute","year":"2019","unstructured":"Klute, F., N\u00f6llenburg, M.: Minimizing crossings in constrained two-sided circular graph layouts. J. Comput. Geom. 10(2), 45\u201369 (2019)","journal-title":"J. Comput. Geom."},{"key":"39_CR17","doi-asserted-by":"crossref","unstructured":"Overmars, M.H., Welzl, E.: New methods for computing visibility graphs. In: Proceedings of the Fourth Annual Symposium on Computational Geometry, pp. 164\u2013171 (1988)","DOI":"10.1145\/73393.73410"},{"issue":"4","key":"39_CR18","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1007\/s00454-006-1264-9","volume":"36","author":"J Pach","year":"2006","unstructured":"Pach, J., Radoicic, R., Tardos, G., Toth, G.: Improving the crossing lemma by finding more crossings in sparse graphs. Discret. Comput. Geom. 36(4), 527\u2013552 (2006). https:\/\/doi.org\/10.1007\/s00454-006-1264-9","journal-title":"Discret. Comput. Geom."},{"issue":"3","key":"39_CR19","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1007\/BF01215922","volume":"17","author":"J Pach","year":"1997","unstructured":"Pach, J., T\u00f3th, G.: Graphs drawn with few crossings per edge. Combinatorica 17(3), 427\u2013439 (1997). https:\/\/doi.org\/10.1007\/BF01215922","journal-title":"Combinatorica"},{"key":"39_CR20","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1007\/BF02712876","volume":"16","author":"M Pocchiola","year":"1996","unstructured":"Pocchiola, M., Vegter, G.: Topologically sweeping visibility complexes via pseudotriangulations. Discret. Comput. Geom. 16, 419\u2013453 (1996)","journal-title":"Discret. Comput. Geom."},{"issue":"5","key":"39_CR21","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1006\/jvlc.2002.0232","volume":"13","author":"HC Purchase","year":"2002","unstructured":"Purchase, H.C.: Metrics for graph drawing aesthetics. J. Vis. Lang. Comput. 13(5), 501\u2013516 (2002)","journal-title":"J. Vis. Lang. Comput."},{"key":"39_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3325861","volume":"24","author":"M Radermacher","year":"2019","unstructured":"Radermacher, M., Reichard, K., Rutter, I., Wagner, D.: Geometric heuristics for rectilinear crossing minimization. J. Exp. Algorithmics (JEA) 24, 1\u201321 (2019)","journal-title":"J. Exp. Algorithmics (JEA)"},{"key":"39_CR23","doi-asserted-by":"publisher","unstructured":"Shamos, M.I., Hoey, D.: Geometric intersection problems. In: 17th Annual Symposium on Foundations of Computer Science (SFCS 1976), pp. 208\u2013215 (1976). https:\/\/doi.org\/10.1109\/SFCS.1976.16","DOI":"10.1109\/SFCS.1976.16"},{"key":"39_CR24","doi-asserted-by":"crossref","unstructured":"Teller, S., Hanrahan, P.: Global visibility algorithms for illumination computations. In: Proceedings of the 20th Annual Conference on Computer Graphics and Interactive Techniques, pp. 239\u2013246 (1993)","DOI":"10.1145\/166117.166148"},{"issue":"1","key":"39_CR25","doi-asserted-by":"publisher","first-page":"890","DOI":"10.1109\/TVCG.2021.3114865","volume":"28","author":"Y Zhao","year":"2021","unstructured":"Zhao, Y., Wang, Y., Zhang, J., Fu, C.W., Xu, M., Moritz, D.: KD-box: line-segment-based KD-tree for interactive exploration of large-scale time-series data. IEEE Trans. Vis. Comput. Graph. 28(1), 890\u2013900 (2021)","journal-title":"IEEE Trans. Vis. Comput. Graph."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-63021-7_39","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,21]],"date-time":"2024-06-21T13:18:58Z","timestamp":1718975938000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-63021-7_39"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031630200","9783031630217"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-63021-7_39","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"22 June 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"IWOCA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Combinatorial Algorithms","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Ischia","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"1 July 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"3 July 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"35","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"iwoca2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/iwoca2024.di.unisa.it","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}