{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T23:23:22Z","timestamp":1778887402605,"version":"3.51.4"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2023,9,26]],"date-time":"2023-09-26T00:00:00Z","timestamp":1695686400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["RU-1903\/3-1"],"award-info":[{"award-number":["RU-1903\/3-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2023,10,31]]},"abstract":"<jats:p>\n            We introduce the problem S\n            <jats:sc>ynchronized<\/jats:sc>\n            P\n            <jats:sc>lanarity<\/jats:sc>\n            . Roughly speaking, its input is a loop-free multi-graph together with synchronization constraints that, e.g., match pairs of vertices of equal degree by providing a bijection between their edges. S\n            <jats:sc>ynchronized<\/jats:sc>\n            P\n            <jats:sc>lanarity<\/jats:sc>\n            then asks whether the graph admits a crossing-free embedding into the plane such that the orders of edges around synchronized vertices are consistent. We show, on the one hand, that S\n            <jats:sc>ynchronized<\/jats:sc>\n            P\n            <jats:sc>lanarity<\/jats:sc>\n            can be solved in quadratic time, and, on the other hand, that it serves as a powerful modeling language that lets us easily formulate several constrained planarity problems as instances of S\n            <jats:sc>ynchronized<\/jats:sc>\n            P\n            <jats:sc>lanarity<\/jats:sc>\n            . In particular, this lets us solve C\n            <jats:sc>lustered<\/jats:sc>\n            P\n            <jats:sc>lanarity<\/jats:sc>\n            in quadratic time, where the most efficient previously known algorithm has an upper bound of\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>8<\/jats:sup>\n            ).\n          <\/jats:p>","DOI":"10.1145\/3607474","type":"journal-article","created":{"date-parts":[[2023,8,3]],"date-time":"2023-08-03T12:01:00Z","timestamp":1691064060000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Synchronized Planarity with Applications to Constrained Planarity Problems"],"prefix":"10.1145","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2450-744X","authenticated-orcid":false,"given":"Thomas","family":"Bl\u00e4sius","sequence":"first","affiliation":[{"name":"Karlsruhe Institute of Technology (KIT), Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2754-1195","authenticated-orcid":false,"given":"Simon D.","family":"Fink","sequence":"additional","affiliation":[{"name":"University of Passau, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3794-4406","authenticated-orcid":false,"given":"Ignaz","family":"Rutter","sequence":"additional","affiliation":[{"name":"University of Passau, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,9,26]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/3344549"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxw035"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-018-00541-w"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-017-0301-9"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2015.02.002"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/2738054"},{"key":"e_1_3_2_8_2","first-page":"349","volume-title":"Proceedings of the Handbook of Graph Drawing and Visualization","author":"Bl\u00e4sius Thomas","year":"2013","unstructured":"Thomas Bl\u00e4sius, Stephen G. Kobourov, and Ignaz Rutter. 2013. Simultaneous embedding of planar graphs. In Proceedings of the Handbook of Graph Drawing and Visualization. Roberto Tamassia (Ed.), CRC, Taylor and Francis Group, Chapter 11, 349\u2013381."},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.10.011"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.5555\/908019"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/s0022-0000(76)80045-1"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2006.05.006"},{"key":"e_1_3_2_13_2","unstructured":"Johannes Carmesin. 2017. Embedding simply connected 2-complexes in 3-space \u2013 I. A Kuratowski-type characterisation. arXiv:1709.04642. Retrieved from https:\/\/arxiv.org\/abs\/1709.04642"},{"key":"e_1_3_2_14_2","unstructured":"Johannes Carmesin. 2017. Embedding simply connected 2-complexes in 3-space \u2013 II. Rotation systems. arXiv:1709.04643. Retrieved from https:\/\/arxiv.org\/abs\/1709.04643"},{"key":"e_1_3_2_15_2","unstructured":"Johannes Carmesin. 2017. Embedding simply connected 2-complexes in 3-space \u2013 V. A refined Kuratowski-type characterisation. arXiv:1709.04659. Retrieved from https:\/\/arxiv.org\/abs\/1709.04659"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00165"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-04414-5_2"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00461"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(90)90045-Y"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/bf01961541"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53622-3"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794269072"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/bfb0030816"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-60313-1_145"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.37236\/5002"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3502264"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-36151-0_21"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00160"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44541-2_8"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1137\/0204019"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1109\/tvcg.2007.70582"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384249"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.146"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1137\/0202012"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44679-6_23"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00184"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/65950.65952"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2021.05.012"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100043279"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00298"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1016\/s0304-3975(98)00120-0"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1201\/b15385"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3607474","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3607474","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:37:35Z","timestamp":1750178255000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3607474"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,26]]},"references-count":41,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,10,31]]}},"alternative-id":["10.1145\/3607474"],"URL":"https:\/\/doi.org\/10.1145\/3607474","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,9,26]]},"assertion":[{"value":"2022-07-15","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-06-21","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-09-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}