{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:19:13Z","timestamp":1740122353929,"version":"3.37.3"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2021,4,10]],"date-time":"2021-04-10T00:00:00Z","timestamp":1618012800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,4,10]],"date-time":"2021-04-10T00:00:00Z","timestamp":1618012800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000121","name":"Division of Mathematical Sciences","doi-asserted-by":"publisher","award":["1603823","1604458"],"award-info":[{"award-number":["1603823","1604458"]}],"id":[{"id":"10.13039\/100000121","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2022,11]]},"DOI":"10.1007\/s10878-021-00731-3","type":"journal-article","created":{"date-parts":[[2021,4,10]],"date-time":"2021-04-10T07:02:45Z","timestamp":1618038165000},"page":"2302-2323","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Intersections and circuits in sets of line segments"],"prefix":"10.1007","volume":"44","author":[{"given":"Boris","family":"Brimkov","sequence":"first","affiliation":[]},{"given":"Jesse","family":"Geneson","sequence":"additional","affiliation":[]},{"given":"Alathea","family":"Jensen","sequence":"additional","affiliation":[]},{"given":"Jordan","family":"Broussard","sequence":"additional","affiliation":[]},{"given":"Pouria Salehi","family":"Nowbandegani","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,4,10]]},"reference":[{"key":"731_CR1","doi-asserted-by":"crossref","unstructured":"Balaban IJ (1995) An optimal algorithm for finding segment intersections. In Proceedings of the eleventh annual symposium on computational geometry, pp. 211\u2013219","DOI":"10.1145\/220279.220302"},{"issue":"2","key":"731_CR2","doi-asserted-by":"publisher","first-page":"199","DOI":"10.7155\/jgaa.00255","volume":"16","author":"B Ben-Moshe","year":"2012","unstructured":"Ben-Moshe B, Dvir A, Segal M, Tamir A (2012) Centdian computation in cactus graphs. J Gr Algorithms Appl 16(2):199\u2013224","journal-title":"J Gr Algorithms Appl"},{"key":"731_CR3","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1109\/TC.1979.1675432","volume":"9","author":"JL Bentley","year":"1979","unstructured":"Bentley JL, Ottmann TA (1979) Algorithms for reporting and counting geometric intersections. IEEE Trans Computers 9:643\u2013647","journal-title":"IEEE Trans Computers"},{"issue":"3","key":"731_CR4","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/j.comgeo.2006.03.006","volume":"37","author":"P Bose","year":"2007","unstructured":"Bose P, Maheshwari A, Morin P, Morrison J, Smid M, Vahrenhold J (2007) Space-efficient geometric divide-and-conquer algorithms. Comput Geom 37(3):209\u2013227","journal-title":"Comput Geom"},{"key":"731_CR5","doi-asserted-by":"crossref","unstructured":"Br\u00e9villiers M, Chevallier N, Schmitt D (2007) Triangulations of line segment sets in the plane. In International conference on foundations of software technology and theoretical computer science, pp. 388\u2013399","DOI":"10.1007\/978-3-540-77050-3_32"},{"key":"731_CR6","doi-asserted-by":"crossref","unstructured":"Brimkov B (2017) On sets of line segments featuring a cactus structure. In International workshop on combinatorial image analysis, pp. 30\u201339","DOI":"10.1007\/978-3-319-59108-7_3"},{"key":"731_CR7","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1016\/j.dam.2015.10.032","volume":"216","author":"B Brimkov","year":"2017","unstructured":"Brimkov B, Hicks IV (2017) Memory efficient algorithms for cactus graphs and block graphs. Discrete Appl Math 216:393\u2013407","journal-title":"Discrete Appl Math"},{"issue":"8","key":"731_CR8","doi-asserted-by":"publisher","first-page":"1653","DOI":"10.1080\/00207160.2013.775423","volume":"90","author":"VE Brimkov","year":"2013","unstructured":"Brimkov VE (2013) Approximability issues of guarding a set of segments. Int J Computer Math 90(8):1653\u20131667","journal-title":"Int J Computer Math"},{"issue":"15","key":"731_CR9","doi-asserted-by":"publisher","first-page":"1313","DOI":"10.1016\/j.tcs.2010.08.014","volume":"412","author":"VE Brimkov","year":"2011","unstructured":"Brimkov VE, Leach A, Mastroianni M, Wu J (2011) Guarding a set of line segments in the plane. Theor Computer Sci 412(15):1313\u20131324","journal-title":"Theor Computer Sci"},{"key":"731_CR10","doi-asserted-by":"publisher","first-page":"1039","DOI":"10.1016\/j.dam.2011.11.023","volume":"160","author":"VE Brimkov","year":"2012","unstructured":"Brimkov VE, Leach A, Wu J, Mastroianni M (2012) Approximation algorithms for a geometric set cover problem. Discrete Appl Mathematics 160:1039\u20131052","journal-title":"Discrete Appl Mathematics"},{"issue":"8","key":"731_CR11","doi-asserted-by":"publisher","first-page":"636","DOI":"10.1016\/j.comgeo.2010.04.005","volume":"43","author":"TM Chan","year":"2010","unstructured":"Chan TM, Chen EY (2010) Optimal in-place and cache-oblivious algorithms for 3-d convex hulls and 2-d segment intersection. Comput Geom 43(8):636\u2013646","journal-title":"Comput Geom"},{"key":"731_CR12","unstructured":"Chazelle BM (1983) Reporting and counting arbitrary planar intersections. Report CS-83-16, Department of Computer Science, Brown University, Providence, RI, USA"},{"key":"731_CR13","unstructured":"Chen EY, Chan TM (2003) A space-efficient algorithm for line segment intersection. In: Proceedings of the 15th Canadian conference on computational geometry, pp. 68\u201371"},{"issue":"3","key":"731_CR14","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1007\/BF02591867","volume":"26","author":"G Cornu\u00e9jols","year":"1983","unstructured":"Cornu\u00e9jols G, Naddef D, Pulleyblank WR (1983) Halin graphs and the travelling salesman problem. Math Program 26(3):287\u2013294","journal-title":"Math Program"},{"issue":"3","key":"731_CR15","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1016\/j.comgeo.2006.09.002","volume":"38","author":"V Dujmovi\u0107","year":"2007","unstructured":"Dujmovi\u0107 V, Eppstein D, Suderman M, Wood DR (2007) Drawings of planar graphs with few slopes and segments. Comput Geom 38(3):194\u2013212","journal-title":"Comput Geom"},{"issue":"1","key":"731_CR16","doi-asserted-by":"publisher","first-page":"7","DOI":"10.7155\/jgaa.00043","volume":"6","author":"N de Castro","year":"2002","unstructured":"de Castro N, Cobos FJ, Dana JC, M\u00e1rquez A, Noy M (2002) Triangle-free planar graphs and segment intersection graphs. J Gr Algorithms Appl 6(1):7\u201326","journal-title":"J Gr Algorithms Appl"},{"key":"731_CR17","first-page":"40","volume":"77","author":"S Durocher","year":"2018","unstructured":"Durocher S, Mondal D (2018) Drawing plane triangulations with few segments. Comput Geom 77:40\u201345","journal-title":"Comput Geom"},{"issue":"2","key":"731_CR18","doi-asserted-by":"publisher","first-page":"323","DOI":"10.7155\/jgaa.00395","volume":"20","author":"D Eppstein","year":"2016","unstructured":"Eppstein D (2016) Simple recognition of Halin graphs and their generalizations. J Gr Algorithms Appl 20(2):323\u2013346","journal-title":"J Gr Algorithms Appl"},{"issue":"10","key":"731_CR19","doi-asserted-by":"publisher","first-page":"1815","DOI":"10.1016\/j.disc.2012.01.024","volume":"312","author":"MC Francis","year":"2012","unstructured":"Francis MC, Kratochv\u00edl J, Vysko\u010dil T (2012) Segment representation of a subclass of co-planar graphs. Discrete Math 312(10):1815\u20131818","journal-title":"Discrete Math"},{"issue":"2","key":"731_CR20","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1007\/s00454-013-9518-9","volume":"50","author":"B Green","year":"2013","unstructured":"Green B, Tao T (2013) On sets defining few ordinary lines. Discrete Comput Geom 50(2):409\u2013468","journal-title":"Discrete Comput Geom"},{"key":"731_CR21","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1073\/pnas.39.4.315","volume":"39","author":"F Harary","year":"1953","unstructured":"Harary F, Uhlenbeck G (1953) On the number of Husimi trees: I. Proc Nat Acad Sci 39:315\u2013322","journal-title":"Proc Nat Acad Sci"},{"issue":"1","key":"731_CR22","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/0166-218X(93)E0131-H","volume":"56","author":"SB Horton","year":"1995","unstructured":"Horton SB, Parker RG (1995) On Halin subgraphs and supergraphs. Discrete Appl Math 56(1):19\u201335","journal-title":"Discrete Appl Math"},{"key":"731_CR23","doi-asserted-by":"publisher","first-page":"682","DOI":"10.1063\/1.1747725","volume":"18","author":"K Husimi","year":"1950","unstructured":"Husimi K (1950) Note on Mayers\u2019 theory of cluster integrals. J Chem Phys 18:682\u2013684","journal-title":"J Chem Phys"},{"key":"731_CR24","doi-asserted-by":"crossref","unstructured":"Igamberdiev, A, Meulemans W, Schulz A (2015) Drawing planar cubic 3-connected graphs with few segments: algorithms and experiments. In International symposium on graph drawing and network visualization, pp. 113\u2013124","DOI":"10.1007\/978-3-319-27261-0_10"},{"key":"731_CR25","doi-asserted-by":"crossref","unstructured":"K\u00e1ra J, Kratochv\u00edl J (2006) Fixed parameter tractability of independent set in segment intersection graphs. In International workshop on parameterized and exact computation, pp. 166\u2013174","DOI":"10.1007\/11847250_15"},{"issue":"3","key":"731_CR26","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1137\/0137040","volume":"37","author":"O Kariv","year":"1979","unstructured":"Kariv O, Hakimi SL (1979) An algorithmic approach to network location problems. I: the p-center. SIAM J Appl Math 37(3):513\u2013538","journal-title":"SIAM J Appl Math"},{"issue":"3","key":"731_CR27","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1002\/j.1538-7305.1980.tb03008.x","volume":"59","author":"WLG Koontz","year":"1980","unstructured":"Koontz WLG (1980) Economic evaluation of loop feeder relief alternatives. Bell Syst Tech J 59(3):277\u2013281","journal-title":"Bell Syst Tech J"},{"key":"731_CR28","unstructured":"Kumar CP (2019) On the regions formed by the diagonals of a convex polygon. arXiv:1904.04065"},{"key":"731_CR29","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/978-3-642-83539-1_11","volume-title":"Theoretical foundations of computer graphics and CAD","author":"HG Mairson","year":"1988","unstructured":"Mairson HG, Stolfi J (1988) Reporting and counting intersections between two sets of line segments. In: Earnshaw RA (ed) Theoretical foundations of computer graphics and CAD. Springer, Berlin, pp 307\u2013325"},{"issue":"6","key":"731_CR30","doi-asserted-by":"publisher","first-page":"111825","DOI":"10.1016\/j.disc.2020.111825","volume":"343","author":"D Oliveros","year":"2020","unstructured":"Oliveros D, O\u2019Neill C, Zerbib S (2020) The geometry and combinatorics of discrete line segment hypergraphs. Discrete Math 343(6):111825","journal-title":"Discrete Math"},{"issue":"1","key":"731_CR31","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1137\/S0895480195281246","volume":"11","author":"B Poonen","year":"1998","unstructured":"Poonen B, Rubinstein M (1998) The number of intersection points made by the diagonals of a regular polygon. SIAM J Discrete Math 11(1):135\u2013156","journal-title":"SIAM J Discrete Math"},{"key":"731_CR32","volume-title":"Computational geometry: an introduction","author":"F Preparata","year":"2012","unstructured":"Preparata F, Shamos MI (2012) Computational geometry: an introduction. Springer, New York"},{"issue":"3","key":"731_CR33","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1007\/BF02187791","volume":"5","author":"D Rappaport","year":"1990","unstructured":"Rappaport D, Imai H, Toussaint GT (1990) Computing simple circuits from a set of line segments. Discrete Comput Geom 5(3):289\u2013304","journal-title":"Discrete Comput Geom"},{"key":"731_CR34","doi-asserted-by":"crossref","unstructured":"Samee MAH, Alam MJ, Adnan MA, Rahman MS (2008) Minimum segment drawings of series-parallel graphs with the maximum degree three. In International symposium on graph drawing, pp. 408\u2013419","DOI":"10.1007\/978-3-642-00219-9_40"},{"key":"731_CR35","doi-asserted-by":"crossref","unstructured":"Sys\u0142o MM, Proskurowski A (1983) On Halin graphs. In: Graph theory, Springer, Berlin, pp 248\u2013256","DOI":"10.1007\/BFb0071635"},{"key":"731_CR36","doi-asserted-by":"publisher","first-page":"722","DOI":"10.1145\/362814.362819","volume":"13","author":"JC Tiernan","year":"1970","unstructured":"Tiernan JC (1970) An efficient search algorithm to find the elementary circuits of a graph. Commun ACM 13:722\u2013726","journal-title":"Commun ACM"},{"key":"731_CR37","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1016\/j.comgeo.2006.09.001","volume":"38","author":"J Vahrenhold","year":"2007","unstructured":"Vahrenhold J (2007) Line-segment intersection made in-place. Comput Geom 38:213\u2013230","journal-title":"Comput Geom"},{"key":"731_CR38","first-page":"26","volume":"46","author":"K Wagner","year":"1936","unstructured":"Wagner K (1936) Bemerkungen zum Vierfarbenproblem. Jahresbericht der Deutschen Mathematiker-Vereinigung 46:26\u201332","journal-title":"Jahresbericht der Deutschen Mathematiker-Vereinigung"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-021-00731-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-021-00731-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-021-00731-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,14]],"date-time":"2022-10-14T20:17:44Z","timestamp":1665778664000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-021-00731-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,10]]},"references-count":38,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,11]]}},"alternative-id":["731"],"URL":"https:\/\/doi.org\/10.1007\/s10878-021-00731-3","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2021,4,10]]},"assertion":[{"value":"31 March 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 April 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}