{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T21:29:32Z","timestamp":1743110972316,"version":"3.40.3"},"publisher-location":"Cham","reference-count":30,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031754081"},{"type":"electronic","value":"9783031754098"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"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":[[2025]]},"DOI":"10.1007\/978-3-031-75409-8_9","type":"book-chapter","created":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T22:10:20Z","timestamp":1737497420000},"page":"121-135","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Augmenting Plane Straight-Line Graphs to\u00a0Meet Parity Constraints"],"prefix":"10.1007","author":[{"given":"Aleksander Bj\u00f8rn Grodt","family":"Christiansen","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3786-916X","authenticated-orcid":false,"given":"Linda","family":"Kleist","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3147-0083","authenticated-orcid":false,"given":"Irene","family":"Parada","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5853-7909","authenticated-orcid":false,"given":"Eva","family":"Rotenberg","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,1,22]]},"reference":[{"issue":"3","key":"9_CR1","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1016\/j.comgeo.2007.09.001","volume":"40","author":"M Abellanas","year":"2008","unstructured":"Abellanas, M., Olaverri, A.G., Hurtado, F., Tejel, J., Urrutia, J.: Augmenting the connectivity of geometric graphs. Comput. Geom. 40(3), 220\u2013230 (2008). https:\/\/doi.org\/10.1016\/j.comgeo.2007.09.001","journal-title":"Comput. Geom."},{"key":"9_CR2","doi-asserted-by":"publisher","unstructured":"Adriaens, F., Gionis, A.: Diameter minimization by shortcutting with degree constraints. In: Zhu, X., Ranka, S., Thai, M.T., Washio, T., Wu, X. (eds.) Proceedings of the IEEE International Conference on Data Mining (ICDM 2022), pp. 843\u2013848. IEEE (2022). https:\/\/doi.org\/10.1109\/ICDM54844.2022.00095","DOI":"10.1109\/ICDM54844.2022.00095"},{"issue":"1","key":"9_CR3","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/s00373-012-1247-y","volume":"30","author":"O Aichholzer","year":"2012","unstructured":"Aichholzer, O., et al.: Plane graphs with parity constraints. Graphs and Combinatorics 30(1), 47\u201369 (2012). https:\/\/doi.org\/10.1007\/s00373-012-1247-y","journal-title":"Graphs and Combinatorics"},{"key":"9_CR4","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1016\/j.tcs.2018.05.031","volume":"789","author":"HA Akitaya","year":"2019","unstructured":"Akitaya, H.A., Inkulu, R., Nichols, T.L., Souvaine, D.L., T\u00f3th, C.D., Winston, C.R.: Minimum weight connectivity augmentation for planar straight-line graphs. Theor. Comput. Sci. 789, 50\u201363 (2019). https:\/\/doi.org\/10.1016\/j.tcs.2018.05.031","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"9_CR5","doi-asserted-by":"publisher","first-page":"971","DOI":"10.1007\/s00453-011-9551-0","volume":"61","author":"M Al-Jubeh","year":"2011","unstructured":"Al-Jubeh, M., Ishaque, M., R\u00e9dei, K., Souvaine, D.L., T\u00f3th, C.D., Valtr, P.: Augmenting the edge connectivity of planar straight line graphs to three. Algorithmica 61(4), 971\u2013999 (2011). https:\/\/doi.org\/10.1007\/s00453-011-9551-0","journal-title":"Algorithmica"},{"issue":"3","key":"9_CR6","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1002\/1097-0118(200011)35:3<161::AID-JGT1>3.0.CO;2-Y","volume":"35","author":"N Alon","year":"2000","unstructured":"Alon, N., Gy\u00e1rf\u00e1s, A., Ruszink\u00f3, M.: Decreasing the diameter of bounded degree graphs. J. Graph Theory 35(3), 161\u2013172 (2000)","journal-title":"J. Graph Theory"},{"issue":"1","key":"9_CR7","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/s00373-013-1389-6","volume":"31","author":"V Alvarez","year":"2013","unstructured":"Alvarez, V.: Parity-constrained triangulations with steiner points. Graphs and Combinatorics 31(1), 35\u201357 (2013). https:\/\/doi.org\/10.1007\/s00373-013-1389-6","journal-title":"Graphs and Combinatorics"},{"issue":"1","key":"9_CR8","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1006\/jagm.2000.1093","volume":"37","author":"AA Bencz\u00far","year":"2000","unstructured":"Bencz\u00far, A.A., Karger, D.R.: Augmenting undirected edge connectivity in $${\\tilde{O}}(n^2)$$ time. J. Algorithms 37(1), 2\u201336 (2000). https:\/\/doi.org\/10.1006\/jagm.2000.1093","journal-title":"J. Algorithms"},{"key":"9_CR9","doi-asserted-by":"publisher","first-page":"125513","DOI":"10.1016\/j.amc.2020.125513","volume":"386","author":"JC Catana","year":"2020","unstructured":"Catana, J.C., Olaverri, A.G., Tejel, J., Urrutia, J.: Plane augmentation of plane graphs to meet parity constraints. Appl. Math. Comput. 386, 125513 (2020). https:\/\/doi.org\/10.1016\/j.amc.2020.125513","journal-title":"Appl. Math. Comput."},{"key":"9_CR10","doi-asserted-by":"publisher","unstructured":"Cen, R., Li, J., Panigrahi, D.: Augmenting edge connectivity via isolating cuts. In: Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms (SODA 2022), pp. 3237\u20133252. SIAM (2022). https:\/\/doi.org\/10.1137\/1.9781611977073.127","DOI":"10.1137\/1.9781611977073.127"},{"issue":"1","key":"9_CR11","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1007\/BF01377183","volume":"12","author":"B Chazelle","year":"1994","unstructured":"Chazelle, B., et al.: Ray shooting in polygons using geodesic triangulations. Algorithmica 12(1), 54\u201368 (1994). https:\/\/doi.org\/10.1007\/BF01377183","journal-title":"Algorithmica"},{"issue":"4","key":"9_CR12","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1002\/jgt.3190080408","volume":"8","author":"FRK Chung","year":"1984","unstructured":"Chung, F.R.K., Garey, M.R.: Diameter bounds for altered graphs. J. Graph Theory 8(4), 511\u2013534 (1984). https:\/\/doi.org\/10.1002\/jgt.3190080408","journal-title":"J. Graph Theory"},{"key":"9_CR13","doi-asserted-by":"publisher","unstructured":"Dabrowski, K.K., Golovach, P.A., van \u2019t Hof, P., Paulusma, D.: Editing to Eulerian graphs. J. Comput. Syst. Sci. 82(2), 213\u2013228 (2016). https:\/\/doi.org\/10.1016\/j.jcss.2015.10.003","DOI":"10.1016\/j.jcss.2015.10.003"},{"issue":"1","key":"9_CR14","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/BF01580113","volume":"5","author":"J Edmonds","year":"1973","unstructured":"Edmonds, J., Johnson, E.L.: Matching, euler tours and the Chinese postman. Math. Program. 5(1), 88\u2013124 (1973). https:\/\/doi.org\/10.1007\/BF01580113","journal-title":"Math. Program."},{"issue":"4","key":"9_CR15","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1137\/0205044","volume":"5","author":"KP Eswaran","year":"1976","unstructured":"Eswaran, K.P., Tarjan, R.E.: Augmentation problems. SIAM J. Comput. 5(4), 653\u2013665 (1976). https:\/\/doi.org\/10.1137\/0205044","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9_CR16","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1137\/0405003","volume":"5","author":"A Frank","year":"1992","unstructured":"Frank, A.: Augmenting graphs to meet edge-connectivity requirements. SIAM J. Discret. Math. 5(1), 25\u201353 (1992). https:\/\/doi.org\/10.1137\/0405003","journal-title":"SIAM J. Discret. Math."},{"issue":"4","key":"9_CR17","doi-asserted-by":"publisher","first-page":"995","DOI":"10.1007\/s00453-014-9886-4","volume":"72","author":"F Frati","year":"2014","unstructured":"Frati, F., Gaspers, S., Gudmundsson, J., Mathieson, L.: Augmenting graphs to minimize the diameter. Algorithmica 72(4), 995\u20131010 (2014). https:\/\/doi.org\/10.1007\/s00453-014-9886-4","journal-title":"Algorithmica"},{"issue":"5","key":"9_CR18","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1016\/j.comgeo.2013.12.009","volume":"47","author":"A Garc\u00eda","year":"2014","unstructured":"Garc\u00eda, A., Huemer, C., Hurtado, F., Tejel, J.: Compatible spanning trees. Comput. Geom. 47(5), 563\u2013584 (2014). https:\/\/doi.org\/10.1016\/j.comgeo.2013.12.009","journal-title":"Comput. Geom."},{"issue":"2","key":"9_CR19","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1007\/s00373-015-1547-0","volume":"31","author":"A Garc\u00eda","year":"2015","unstructured":"Garc\u00eda, A., et al.: Geometric biplane graphs II: graph augmentation. Graphs and Combinatorics 31(2), 427\u2013452 (2015). https:\/\/doi.org\/10.1007\/s00373-015-1547-0","journal-title":"Graphs and Combinatorics"},{"issue":"1","key":"9_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1142\/S0218195991000025","volume":"1","author":"LJ Guibas","year":"1991","unstructured":"Guibas, L.J., Hershberger, J., Snoeyink, J.: Compact interval trees: a data structure for convex hulls. Int. J. Comput. Geom. Appl. 1(1), 1\u201322 (1991). https:\/\/doi.org\/10.1142\/S0218195991000025","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"3","key":"9_CR21","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1137\/0204019","volume":"4","author":"F Hadlock","year":"1975","unstructured":"Hadlock, F.: Finding a maximum cut of a planar graph in polynomial time. SIAM J. Comput. 4(3), 221\u2013225 (1975). https:\/\/doi.org\/10.1137\/0204019","journal-title":"SIAM J. Comput."},{"key":"9_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"286","DOI":"10.1007\/BFb0028270","volume-title":"Algorithms and Data Structures","author":"G Kant","year":"1991","unstructured":"Kant, G., Bodlaender, H.L.: Planar graph augmentation problems. In: Dehne, F., Sack, J.-R., Santoro, N. (eds.) WADS 1991. LNCS, vol. 519, pp. 286\u2013298. Springer, Heidelberg (1991). https:\/\/doi.org\/10.1007\/BFb0028270"},{"key":"9_CR23","doi-asserted-by":"publisher","unstructured":"Kranakis, E., Krizanc, D., Morales-Ponce, O., Stacho, L.: Bounded length, 2-edge augmentation of geometric planar graphs. Discret. Math. Algorithms Appl. 4(3) (2012). https:\/\/doi.org\/10.1142\/S179383091250036X","DOI":"10.1142\/S179383091250036X"},{"key":"9_CR24","first-page":"273","volume":"1","author":"MK Kwan","year":"1960","unstructured":"Kwan, M.K.: Graphic programming using odd or even points. Chinese Math 1, 273\u2013277 (1960)","journal-title":"Chinese Math"},{"issue":"1","key":"9_CR25","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/0020-0190(87)90086-X","volume":"25","author":"AA Melkman","year":"1987","unstructured":"Melkman, A.A.: On-line construction of the convex hull of a simple polyline. Inf. Process. Lett. 25(1), 11\u201312 (1987). https:\/\/doi.org\/10.1016\/0020-0190(87)90086-X","journal-title":"Inf. Process. Lett."},{"key":"9_CR26","doi-asserted-by":"publisher","first-page":"555","DOI":"10.4153\/CJM-1960-049-6","volume":"12","author":"CSJA Nash-Williams","year":"1960","unstructured":"Nash-Williams, C.S.J.A.: On orientations, connectivity and odd-vertex-pairings in finite graphs. Can. J. Math. 12, 555\u2013567 (1960). https:\/\/doi.org\/10.4153\/CJM-1960-049-6","journal-title":"Can. J. Math."},{"key":"9_CR27","doi-asserted-by":"publisher","unstructured":"Pilz, A., Rollin, J., Schlipf, L., Schulz, A.: Augmenting geometric graphs with matchings. In: Proceedings of the 28th International Symposium on Graph Drawing and Network Visualization (GD 2020). LNCS, vol. 12590, pp. 490\u2013504. Springer (2020). https:\/\/doi.org\/10.1007\/978-3-030-68766-3_38","DOI":"10.1007\/978-3-030-68766-3_38"},{"issue":"6","key":"9_CR28","doi-asserted-by":"publisher","first-page":"668","DOI":"10.1007\/BF01224737","volume":"27","author":"J Plesn\u00edk","year":"1976","unstructured":"Plesn\u00edk, J.: Minimum block containing a given graph. Arch. Math. 27(6), 668\u2013672 (1976)","journal-title":"Arch. Math."},{"issue":"2","key":"9_CR29","doi-asserted-by":"publisher","first-page":"599","DOI":"10.7155\/jgaa.00275","volume":"16","author":"I Rutter","year":"2012","unstructured":"Rutter, I., Wolff, A.: Augmenting the connectivity of planar and geometric graphs. J. Graph Algorithms Appl. 16(2), 599\u2013628 (2012). https:\/\/doi.org\/10.7155\/jgaa.00275","journal-title":"J. Graph Algorithms Appl."},{"issue":"3","key":"9_CR30","doi-asserted-by":"publisher","first-page":"408","DOI":"10.1016\/j.ejc.2011.09.002","volume":"33","author":"CD T\u00f3th","year":"2012","unstructured":"T\u00f3th, C.D.: Connectivity augmentation in planar straight line graphs. Eur. J. Comb. 33(3), 408\u2013425 (2012). https:\/\/doi.org\/10.1016\/j.ejc.2011.09.002","journal-title":"Eur. J. Comb."}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-75409-8_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T22:10:22Z","timestamp":1737497422000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-75409-8_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031754081","9783031754098"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-75409-8_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"22 January 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WG","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Graph-Theoretic Concepts in Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Gozd Martuljek","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Slovenia","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":"19 June 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 June 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"50","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wg2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/conferences.famnit.upr.si\/event\/31\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}