{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,27]],"date-time":"2023-10-27T11:14:42Z","timestamp":1698405282946},"reference-count":25,"publisher":"World Scientific Pub Co Pte Ltd","issue":"07","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2023,11]]},"abstract":"<jats:p> We study the problem of drawing simultaneously embedded graphs with few bends. We show that for any simultaneous embedding with fixed edges (SEFE) of two graphs, there exists a corresponding drawing realizing this embedding such that common edges are drawn as straight-line segments and each exclusive edge has a constant number of bends. If the common graph is biconnected and induced, a straight-line drawing exists. This yields the first efficient testing algorithm for simultaneous geometric embedding (SGE) for a non-trivial class of graphs. <\/jats:p>","DOI":"10.1142\/s0129054123420017","type":"journal-article","created":{"date-parts":[[2023,5,9]],"date-time":"2023-05-09T16:39:48Z","timestamp":1683650388000},"page":"807-824","source":"Crossref","is-referenced-by-count":0,"title":["Drawing Simultaneously Embedded Graphs with Few Bends"],"prefix":"10.1142","volume":"34","author":[{"given":"Luca","family":"Grilli","sequence":"first","affiliation":[{"name":"Dipartimento di Ingegneria, Universit\u00e0 degli Studi di Perugia, Via G. Duranti 93, 06125 Perugia, Italia"}]},{"given":"Seok-Hee","family":"Hong","sequence":"additional","affiliation":[{"name":"School of Computer Science, University of Sydney, Camperdown NSW 2006, Australia"}]},{"given":"Jan","family":"Kratochv\u00edl","sequence":"additional","affiliation":[{"name":"Department of Applied Mathematics, Faculty of Mathematics and Physics, Charles University, Malostransk\u00e9 n\u00e1m. 25, Prague CZ-11800, Czechia"}]},{"given":"Ignaz","family":"Rutter","sequence":"additional","affiliation":[{"name":"Faculty of Computer Science and Mathematics, University of Passau, Innstra\u00dfe 33, 94032 Passau, Germany"}]}],"member":"219","published-online":{"date-parts":[[2023,5,9]]},"reference":[{"key":"S0129054123420017BIB001","first-page":"202","volume-title":"Discrete Algorithms (SODA\u201910)","author":"Angelini P.","year":"2010"},{"key":"S0129054123420017BIB002","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1016\/j.jda.2011.12.015","volume":"14","author":"Angelini P.","year":"2012","journal-title":"J. Discrete Alg."},{"issue":"1","key":"S0129054123420017BIB003","doi-asserted-by":"crossref","first-page":"37","DOI":"10.7155\/jgaa.00250","volume":"16","author":"Angelini P.","year":"2012","journal-title":"J. Graph Algorithms Appl."},{"key":"S0129054123420017BIB004","series-title":"LIPIcs","first-page":"19:1","volume-title":"Proceedings of the 29th Annual European Symposium on Algorithms (ESA\u201921)","volume":"204","author":"Bl\u00e4sius T.","year":"2021"},{"key":"S0129054123420017BIB005","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"220","DOI":"10.1007\/978-3-319-03841-4_20","volume-title":"Graph Drawing (GD\u201913)","volume":"8242","author":"Bl\u00e4sius T.","year":"2013"},{"key":"S0129054123420017BIB006","volume-title":"Handbook of Graph Drawing and Visualization","author":"Bl\u00e4sius T.","year":"2013"},{"key":"S0129054123420017BIB007","first-page":"1030","volume-title":"Discrete Algorithms (SODA\u201913)","author":"Bl\u00e4sius T.","year":"2013"},{"issue":"2","key":"S0129054123420017BIB008","doi-asserted-by":"crossref","first-page":"681","DOI":"10.7155\/jgaa.00375","volume":"19","author":"Chan T. M.","year":"2015","journal-title":"J. Graph Algorithms Appl."},{"issue":"3","key":"S0129054123420017BIB009","doi-asserted-by":"crossref","first-page":"347","DOI":"10.7155\/jgaa.00113","volume":"9","author":"Erten C.","year":"2005","journal-title":"J. Graph Algorithms Appl."},{"key":"S0129054123420017BIB010","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1007\/978-3-540-77537-9_28","volume-title":"Graph Drawing (GD\u201907)","volume":"4875","author":"Estrella-Balderrama A.","year":"2008"},{"issue":"4","key":"S0129054123420017BIB011","doi-asserted-by":"crossref","first-page":"683","DOI":"10.7155\/jgaa.00507","volume":"23","author":"Frati F.","year":"2019","journal-title":"J. Graph Algorithms Appl."},{"issue":"2","key":"S0129054123420017BIB012","doi-asserted-by":"crossref","first-page":"13:1","DOI":"10.1145\/3502264","volume":"69","author":"Fulek R.","year":"2022","journal-title":"J. ACM"},{"key":"S0129054123420017BIB013","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1007\/11917496_29","volume-title":"Graph-Theoretic Concepts in Computer Science (WG\u201906)","volume":"4271","author":"Gassner E.","year":"2006"},{"key":"S0129054123420017BIB014","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1007\/978-3-662-45803-7_4","volume-title":"Graph Drawing - 22nd International Symposium, GD 2014, W\u00fcrzburg, Germany, September 24-26, 2014, Revised Selected Papers","volume":"8871","author":"Grilli L.","year":"2014"},{"issue":"3","key":"S0129054123420017BIB015","doi-asserted-by":"crossref","first-page":"147","DOI":"10.7155\/jgaa.00289","volume":"17","author":"Haeupler B.","year":"2013","journal-title":"J. Graph Algorithms Appl."},{"issue":"12","key":"S0129054123420017BIB016","doi-asserted-by":"crossref","first-page":"2368","DOI":"10.1016\/j.dam.2007.10.012","volume":"156","author":"Hong S.-H.","year":"2008","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"S0129054123420017BIB017","doi-asserted-by":"crossref","first-page":"466","DOI":"10.1016\/j.comgeo.2012.07.005","volume":"46","author":"Jel\u00ednek V.","year":"2013","journal-title":"Computational Geometry Theory & Applications"},{"issue":"2","key":"S0129054123420017BIB018","doi-asserted-by":"crossref","first-page":"205","DOI":"10.7155\/jgaa.00184","volume":"13","author":"J\u00fcnger M.","year":"2009","journal-title":"J. Graph Algorithms Appl."},{"issue":"1","key":"S0129054123420017BIB019","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0095-8956(91)90050-T","volume":"53","author":"Kratochv\u00edl J.","year":"1991","journal-title":"J. Comb. Theory, Ser. B"},{"key":"S0129054123420017BIB020","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"316","DOI":"10.1007\/978-3-319-03841-4_28","volume-title":"Graph Drawing (GD\u201913)","volume":"8242","author":"Mchedlidze T.","year":"2013"},{"key":"S0129054123420017BIB021","doi-asserted-by":"crossref","first-page":"717","DOI":"10.1007\/PL00007258","volume":"17","author":"Pach J.","year":"2001","journal-title":"Graphs and Combinatorics"},{"issue":"5","key":"S0129054123420017BIB022","doi-asserted-by":"crossref","first-page":"1061","DOI":"10.1142\/S0129054106004261","volume":"17","author":"Patrignani M.","year":"2006","journal-title":"International Journal of Foundations of Computer Science"},{"key":"S0129054123420017BIB023","series-title":"Communications of NII Shonan Meetings","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1007\/978-981-15-6533-5_13","volume-title":"Beyond Planar Graphs","author":"Rutter I.","year":"2020"},{"issue":"4","key":"S0129054123420017BIB024","doi-asserted-by":"crossref","first-page":"367","DOI":"10.7155\/jgaa.00298","volume":"17","author":"Schaefer M.","year":"2013","journal-title":"J. Graph Algorithms Appl."},{"issue":"1","key":"S0129054123420017BIB025","doi-asserted-by":"crossref","first-page":"743","DOI":"10.1112\/plms\/s3-13.1.743","volume":"3","author":"Tutte W. T.","year":"1963","journal-title":"London Math. Soc."}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054123420017","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,26]],"date-time":"2023-10-26T04:52:57Z","timestamp":1698295977000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0129054123420017"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,9]]},"references-count":25,"journal-issue":{"issue":"07","published-print":{"date-parts":[[2023,11]]}},"alternative-id":["10.1142\/S0129054123420017"],"URL":"https:\/\/doi.org\/10.1142\/s0129054123420017","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,9]]}}}