{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:32:24Z","timestamp":1767339144497,"version":"3.41.0"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2015,4,13]],"date-time":"2015-04-13T00:00:00Z","timestamp":1428883200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"fellowship within the postdoctoral program of the German Academic Exchange Service (DAAD)"},{"name":"Australian Research Council","award":["DE140100708"],"award-info":[{"award-number":["DE140100708"]}]},{"name":"ESF EuroGIGA GraDR as Czech Research","award":["GACR GIG-11-E023"],"award-info":[{"award-number":["GACR GIG-11-E023"]}]},{"name":"MIUR project AMANDA (Algorithmics for Massive and Networked Data) protocol 2012C4E3KT_001"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2015,6,23]]},"abstract":"<jats:p>\n            We study the following problem: given a planar graph\n            <jats:italic>G<\/jats:italic>\n            and a planar drawing (embedding) of a subgraph of\n            <jats:italic>G<\/jats:italic>\n            , can such a drawing be extended to a planar drawing of the entire graph\n            <jats:italic>G<\/jats:italic>\n            ? This problem fits the paradigm of extending a partial solution for a problem to a complete one, which has been studied before in many different settings. Unlike many cases, in which the presence of a partial solution in the input makes an otherwise easy problem hard, we show that the planarity question remains polynomial-time solvable. Our algorithm is based on several combinatorial lemmas, which show that the planarity of partially embedded graphs exhibits the \u2018TONCAS\u2019 behavior \u201cthe obvious necessary conditions for planarity are also sufficient.\u201d These conditions are expressed in terms of the interplay between (1) the rotation system and containment relationships between cycles and (2) the decomposition of a graph into its connected, biconnected, and triconnected components. This implies that no dynamic programming is needed for a decision algorithm and that the elements of the decomposition can be processed independently.\n          <\/jats:p>\n          <jats:p>Further, by equipping the components of the decomposition with suitable data structures and by carefully splitting the problem into simpler subproblems, we make our algorithm run in linear time.<\/jats:p>\n          <jats:p>\n            Finally, we consider several generalizations of the problem, such as minimizing the number of edges of the partial embedding that need to be rerouted to extend it, and argue that they are NP-hard. We also apply our algorithm to the simultaneous graph drawing problem\n            <jats:sc>Simultaneous Embedding with Fixed Edges (Sefe)<\/jats:sc>\n            . There we obtain a linear-time algorithm for the case that one of the input graphs or the common graph has a fixed planar embedding.\n          <\/jats:p>","DOI":"10.1145\/2629341","type":"journal-article","created":{"date-parts":[[2015,4,14]],"date-time":"2015-04-14T12:32:19Z","timestamp":1429014739000},"page":"1-42","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":33,"title":["Testing Planarity of Partially Embedded Graphs"],"prefix":"10.1145","volume":"11","author":[{"given":"Patrizio","family":"Angelini","sequence":"first","affiliation":[{"name":"Roma Tre University, Rome, Italy"}]},{"given":"Giuseppe","family":"Di Battista","sequence":"additional","affiliation":[{"name":"Roma Tre University, Rome, Italy"}]},{"given":"Fabrizio","family":"Frati","sequence":"additional","affiliation":[{"name":"University of Sydney, NSW, Sydney, Australia"}]},{"given":"V\u00edt","family":"Jel\u00ednek","sequence":"additional","affiliation":[{"name":"Charles University, Prague, Czech Republic"}]},{"given":"Jan","family":"Kratochv\u00edl","sequence":"additional","affiliation":[{"name":"Charles University, Prague, Czech Republic"}]},{"given":"Maurizio","family":"Patrignani","sequence":"additional","affiliation":[{"name":"Roma Tre University, Rome, Italy"}]},{"given":"Ignaz","family":"Rutter","sequence":"additional","affiliation":[{"name":"Karlsruhe Institute of Technology (KIT), Germany and Charles University, Prague, Karlsruhe, Germany"}]}],"member":"320","published-online":{"date-parts":[[2015,4,13]]},"reference":[{"volume-title":"Proceedings of SODA\u201910","author":"Angelini P.","key":"e_1_2_1_1_1","unstructured":"P. Angelini , G. Di Battista , F. Frati , V. Jel\u00ednek , J. Kratochv\u00edl , M. Patrignani , and I. Rutter . 2010. Testing planarity of partially embedded graphs . In Proceedings of SODA\u201910 . 202--221. P. Angelini, G. Di Battista, F. Frati, V. Jel\u00ednek, J. Kratochv\u00edl, M. Patrignani, and I. Rutter. 2010. Testing planarity of partially embedded graphs. In Proceedings of SODA\u201910. 202--221."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2011.12.015"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00250"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.868028"},{"key":"e_1_2_1_5_1","volume-title":"Graph Drawing. Lecture Notes in Computer Science","volume":"8242","author":"Bl\u00e4sius T.","unstructured":"T. Bl\u00e4sius , A. Karrer , and I. Rutter . 2013a. Simultaneous embedding: Edge orderings, relative positions, cutvertices . In Graph Drawing. Lecture Notes in Computer Science , Vol. 8242 . Springer, 220--231. T. Bl\u00e4sius, A. Karrer, and I. Rutter. 2013a. Simultaneous embedding: Edge orderings, relative positions, cutvertices. In Graph Drawing. Lecture Notes in Computer Science, Vol. 8242. Springer, 220--231."},{"key":"e_1_2_1_6_1","unstructured":"T. Bl\u00e4sius S. G. Kobourov and I. Rutter. 2013b. Simultaneous embedding of planar graphs. In Handbook of Graph Drawing and Visualization R. Tamassia (Ed.). CRC Press.  T. Bl\u00e4sius S. G. Kobourov and I. Rutter. 2013b. Simultaneous embedding of planar graphs. In Handbook of Graph Drawing and Visualization R. Tamassia (Ed.). CRC Press."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36763-2_4"},{"volume-title":"Proceedings of SODA\u201913","author":"Bl\u00e4sius T.","key":"e_1_2_1_8_1","unstructured":"T. Bl\u00e4sius and I. Rutter . 2013b. Simultaneous pq-ordering with applications to constrained embedding problems . In Proceedings of SODA\u201913 . 1030--1043. T. Bl\u00e4sius and I. Rutter. 2013b. Simultaneous pq-ordering with applications to constrained embedding problems. In Proceedings of SODA\u201913. 1030--1043."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00091"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054106004248"},{"key":"e_1_2_1_11_1","first-page":"33","article-title":"Reconnaissance et construction de repr\u00e9sentations planaires topologiques","volume":"8","author":"Demoucron G.","year":"1964","unstructured":"G. Demoucron , Y. Malgrange , and R. Pertuiset . 1964 . Reconnaissance et construction de repr\u00e9sentations planaires topologiques . Rev. Francaise Recherche Op\u00e9rationelle 8 , 33 -- 34 . G. Demoucron, Y. Malgrange, and R. Pertuiset. 1964. Reconnaissance et construction de repr\u00e9sentations planaires topologiques. Rev. Francaise Recherche Op\u00e9rationelle 8, 33--34.","journal-title":"Rev. Francaise Recherche Op\u00e9rationelle"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794280736"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195907002276"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00044"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00113"},{"key":"e_1_2_1_16_1","volume-title":"Graph Drawing. Lecture Notes in Computer Science","volume":"4875","author":"Estrella-Balderrama A.","unstructured":"A. Estrella-Balderrama , E. Gassner , M. J\u00fcnger , M. Percan , M. Schaefer , and M. Schulz . 2007. Simultaneous geometric graph embeddings . In Graph Drawing. Lecture Notes in Computer Science , Vol. 4875 . Springer, 280--290. A. Estrella-Balderrama, E. Gassner, M. J\u00fcnger, M. Percan, M. Schaefer, and M. Schulz. 2007. Simultaneous geometric graph embeddings. In Graph Drawing. Lecture Notes in Computer Science, Vol. 4875. Springer, 280--290."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.v43:2"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2011.02.002"},{"key":"e_1_2_1_19_1","series-title":"Lecture Notes in Computer Science","volume-title":"Graph Drawing","author":"Frati F.","unstructured":"F. Frati . 2006. Embedding graphs simultaneously with fixed edges . In Graph Drawing . Lecture Notes in Computer Science , Vol. 4372 . Springer , 108--113. F. Frati. 2006. Embedding graphs simultaneously with fixed edges. In Graph Drawing. Lecture Notes in Computer Science, Vol. 4372. Springer, 108--113."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/0132071"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/11917496_29"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"M. Gr\u00f6tschel L. Lov\u00e1sz and A. Schrijver. 1988. Stable sets in graphs. In Geometric Algorithms and Combinatorial Optimization. Springer 273--303.  M. Gr\u00f6tschel L. Lov\u00e1sz and A. Schrijver. 1988. Stable sets in graphs. In Geometric Algorithms and Combinatorial Optimization. Springer 273--303.","DOI":"10.1007\/978-3-642-97881-4_10"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00160"},{"key":"e_1_2_1_24_1","volume-title":"Graph Drawing. Lecture Notes in Computer Science","volume":"1984","author":"Gutwenger C.","unstructured":"C. Gutwenger and P. Mutzel . 2000. A linear time implementation of SPQR-trees . In Graph Drawing. Lecture Notes in Computer Science , Vol. 1984 . Springer, 77--90. C. Gutwenger and P. Mutzel. 2000. A linear time implementation of SPQR-trees. In Graph Drawing. Lecture Notes in Computer Science, Vol. 1984. Springer, 77--90."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00289"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/321850.321852"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2012.07.005"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00184"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2004.02.012"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11805-0_21"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33090-2_58"},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","unstructured":"P. Klav\u00edk J. Kratochv\u00edl Y. Otachi I. Rutter T. Saitoh M. Saumell and T. Vysko\u010dil. 2012c. Extending partial representations of proper and unit interval graphs. CoRR abs\/1207.6960.  P. Klav\u00edk J. Kratochv\u00edl Y. Otachi I. Rutter T. Saitoh M. Saumell and T. Vysko\u010dil. 2012c. Extending partial representations of proper and unit interval graphs. CoRR abs\/1207.6960.","DOI":"10.1007\/978-3-642-35261-4_47"},{"key":"e_1_2_1_33_1","volume-title":"Algorithms and Computation. Lecture Notes in Computer Science","volume":"7676","author":"Klav\u00edk P.","unstructured":"P. Klav\u00edk , J. Kratochv\u00edl , Y. Otachi , and T. Saitoh . 2012b. Extending partial representations of subclasses of chordal graphs . In Algorithms and Computation. Lecture Notes in Computer Science , Vol. 7676 . Springer, 444--454. P. Klav\u00edk, J. Kratochv\u00edl, Y. Otachi, and T. Saitoh. 2012b. Extending partial representations of subclasses of chordal graphs. In Algorithms and Computation. Lecture Notes in Computer Science, Vol. 7676. Springer, 444--454."},{"key":"e_1_2_1_34_1","volume-title":"Theory and Applications of Models of Computation. Lecture Notes in Computer Science","volume":"6648","author":"Klav\u00edk P.","unstructured":"P. Klav\u00edk , J. Kratochv\u00edl , and T. Vysko\u010dil . 2011. Extending partial representations of interval graphs . In Theory and Applications of Models of Computation. Lecture Notes in Computer Science , Vol. 6648 . Springer, 276--285. P. Klav\u00edk, J. Kratochv\u00edl, and T. Vysko\u010dil. 2011. Extending partial representations of interval graphs. In Theory and Applications of Models of Computation. Lecture Notes in Computer Science, Vol. 6648. Springer, 276--285."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780565"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0118(199707)25:3%3C207::AID-JGT4%3E3.3.CO;2-X"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.4064\/fm-15-1-271-283"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/S089548019529248X"},{"key":"e_1_2_1_39_1","series-title":"Lecture Notes in Computer Science","volume-title":"Automata, Languages and Programming","author":"Mutzel P.","unstructured":"P. Mutzel . 2003. The SPQR-tree data structure in graph drawing . In Automata, Languages and Programming . Lecture Notes in Computer Science , Vol. 2719 . Springer , 35--46. P. Mutzel. 2003. The SPQR-tree data structure in graph drawing. In Automata, Languages and Programming. Lecture Notes in Computer Science, Vol. 2719. Springer, 35--46."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054106004261"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195439"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00298"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/0216030"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0044"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009760732249"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/21.87055"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/0201010"},{"key":"e_1_2_1_48_1","series-title":"Lecture Notes in Computer Science","volume-title":"Automata, Languages and Programming","author":"Westbrook J.","unstructured":"J. Westbrook . 1992. Fast incremental planarity testing . In Automata, Languages and Programming . Lecture Notes in Computer Science , Vol. 623 . Springer , 342--353. J. Westbrook. 1992. Fast incremental planarity testing. In Automata, Languages and Programming. Lecture Notes in Computer Science, Vol. 623. Springer, 342--353."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629341","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2629341","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:19:30Z","timestamp":1750231170000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629341"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,4,13]]},"references-count":48,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,6,23]]}},"alternative-id":["10.1145\/2629341"],"URL":"https:\/\/doi.org\/10.1145\/2629341","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2015,4,13]]},"assertion":[{"value":"2013-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-04-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}