{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:28:38Z","timestamp":1760441318912,"version":"3.37.3"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2016,2,8]],"date-time":"2016-02-08T00:00:00Z","timestamp":1454889600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003407","name":"Ministero dell\u2019Istruzione, dell\u2019Universit\u00e1 e della Ricerca (IT)","doi-asserted-by":"publisher","award":["2012C4E3KT_001"],"award-info":[{"award-number":["2012C4E3KT_001"]}],"id":[{"id":"10.13039\/501100003407","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft (DE)","doi-asserted-by":"publisher","award":["Ka812\/17-1"],"award-info":[{"award-number":["Ka812\/17-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,4]]},"DOI":"10.1007\/s00453-016-0128-9","type":"journal-article","created":{"date-parts":[[2016,2,8]],"date-time":"2016-02-08T09:18:46Z","timestamp":1454923126000},"page":"1022-1059","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Strip Planarity Testing for Embedded Planar Graphs"],"prefix":"10.1007","volume":"77","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7602-1524","authenticated-orcid":false,"given":"Patrizio","family":"Angelini","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2396-5174","authenticated-orcid":false,"given":"Giordano","family":"Da Lozzo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4224-1550","authenticated-orcid":false,"given":"Giuseppe","family":"Di Battista","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5987-8713","authenticated-orcid":false,"given":"Fabrizio","family":"Frati","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,2,8]]},"reference":[{"issue":"7","key":"128_CR1","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1016\/j.ipl.2010.02.004","volume":"110","author":"S Abbasi","year":"2010","unstructured":"Abbasi, S., Healy, P., Rextin, A.: Improving the running time of embedded upward planarity testing. Inf. Process. Lett. 110(7), 274\u2013278 (2010)","journal-title":"Inf. Process. Lett."},{"key":"128_CR2","doi-asserted-by":"publisher","unstructured":"Aloupis, G., Barba, L., Carmi, P., Dujmovic, V., Frati, F., Morin, P.: Compatible connectivity-augmentation of planar disconnected graphs. In: Indyk, P. (ed.) Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium Discrete Algorithms (SODA \u201915), pp. 1602\u20131615. SIAM, San Diego, CA (2015). doi: 10.1137\/1.9781611973730.106","DOI":"10.1137\/1.9781611973730.106"},{"key":"128_CR3","doi-asserted-by":"crossref","unstructured":"Angelini, P., Di Battista, G., Frati, F., Jel\u00ednek, V., Kratochv\u00edl, J., Patrignani, M., Rutter, I.: Testing planarity of partially embedded graphs. In: Charikar, M. (ed.) ACM-SIAM Symposium on Discrete Algorithms (SODA \u201910). pp. 202\u2013221 (2010)","DOI":"10.1137\/1.9781611973075.19"},{"issue":"1","key":"128_CR4","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1007\/s00454-010-9302-z","volume":"45","author":"P Angelini","year":"2011","unstructured":"Angelini, P., Frati, F., Kaufmann, M.: Straight-line rectangular drawings of clustered graphs. Discrete Comput. Geom. 45(1), 88\u2013140 (2011)","journal-title":"Discrete Comput. Geom."},{"key":"128_CR5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.tcs.2014.12.019","volume":"571","author":"P Angelini","year":"2015","unstructured":"Angelini, P., Da Lozzo, G., Di Battista, G., Frati, F., Roselli, V.: The importance of being proper (in clustered-level planarity and t-level planarity). Theor. Comput. Sci. 571, 1\u20139 (2015)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"128_CR6","doi-asserted-by":"crossref","first-page":"53","DOI":"10.7155\/jgaa.00100","volume":"9","author":"C Bachmaier","year":"2005","unstructured":"Bachmaier, C., Brandenburg, F.J., Forster, M.: Radial level planarity testing and embedding in linear time. J. Graph Algorithms Appl. 9(1), 53\u201397 (2005)","journal-title":"J. Graph Algorithms Appl."},{"issue":"6","key":"128_CR7","doi-asserted-by":"crossref","first-page":"476","DOI":"10.1007\/BF01188716","volume":"12","author":"P Bertolazzi","year":"1994","unstructured":"Bertolazzi, P., Di Battista, G., Liotta, G., Mannino, C.: Upward drawings of triconnected digraphs. Algorithmica 12(6), 476\u2013497 (1994)","journal-title":"Algorithmica"},{"issue":"3","key":"128_CR8","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"KS Booth","year":"1976","unstructured":"Booth, K.S., Lueker, G.S.: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. Syst. Sci. 13(3), 335\u2013379 (1976)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"128_CR9","doi-asserted-by":"crossref","first-page":"243","DOI":"10.7155\/jgaa.00257","volume":"16","author":"EW Chambers","year":"2012","unstructured":"Chambers, E.W., Eppstein, D., Goodrich, M.T., L\u00f6ffler, M.: Drawing graphs in the plane with a prescribed outer face and polynomial area. J. Graph Algorithms Appl. 16(2), 243\u2013259 (2012)","journal-title":"J. Graph Algorithms Appl."},{"key":"128_CR10","first-page":"153","volume-title":"Progress in Graph Theory","author":"N Chiba","year":"1984","unstructured":"Chiba, N., Yamanouchi, T., Nishizeki, T.: Linear algorithms for convex drawings of planar graphs. In: Bondy, J.A., Murty, U.S.R. (eds.) Progress in Graph Theory, pp. 153\u2013173. Academic Press, New York, NY (1984)"},{"key":"128_CR11","doi-asserted-by":"crossref","unstructured":"Chimani, M., Di Battista, G., Frati, F., Klein, K.: Advances on testing c-planarity of embedded flat clustered graphs. In: Duncan, C.A., Symvonis, A. (eds.) Graph Drawing (GD \u201914). LNCS, vol. 8871, pp. 416\u2013427. Springer, Berlin (2014)","DOI":"10.1007\/978-3-662-45803-7_35"},{"issue":"3","key":"128_CR12","doi-asserted-by":"crossref","first-page":"391","DOI":"10.7155\/jgaa.00115","volume":"9","author":"PF Cortese","year":"2005","unstructured":"Cortese, P.F., Di Battista, G., Patrignani, M., Pizzonia, M.: Clustering cycles into cycles of clusters. J. Graph Algorithms Appl. 9(3), 391\u2013413 (2005)","journal-title":"J. Graph Algorithms Appl."},{"issue":"7","key":"128_CR13","doi-asserted-by":"crossref","first-page":"1856","DOI":"10.1016\/j.disc.2007.12.090","volume":"309","author":"PF Cortese","year":"2009","unstructured":"Cortese, P.F., Di Battista, G., Patrignani, M., Pizzonia, M.: On embedding a cycle in a plane graph. Discrete Math. 309(7), 1856\u20131869 (2009)","journal-title":"Discrete Math."},{"issue":"3","key":"128_CR14","doi-asserted-by":"crossref","first-page":"349","DOI":"10.7155\/jgaa.00191","volume":"13","author":"G Battista Di","year":"2009","unstructured":"Di Battista, G., Frati, F.: Efficient c-planarity testing for embedded flat clustered graphs with small faces. J. Graph Algorithms Appl. 13(3), 349\u2013378 (2009)","journal-title":"J. Graph Algorithms Appl."},{"key":"128_CR15","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1016\/0304-3975(88)90123-5","volume":"61","author":"G Battista Di","year":"1988","unstructured":"Di Battista, G., Tamassia, R.: Algorithms for plane representations of acyclic digraphs. Theor. Comput. Sci. 61, 175\u2013198 (1988)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"128_CR16","doi-asserted-by":"crossref","first-page":"1842","DOI":"10.1137\/070696854","volume":"23","author":"W Didimo","year":"2009","unstructured":"Didimo, W., Giordano, F., Liotta, G.: Upward spirality and upward planarity testing. SIAM J. Discrete Math. 23(4), 1842\u20131899 (2009)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"128_CR17","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00453-004-1144-8","volume":"44","author":"P Eades","year":"2006","unstructured":"Eades, P., Feng, Q., Lin, X., Nagamochi, H.: Straight-line drawing algorithms for hierarchical graphs and clustered graphs. Algorithmica 44(1), 1\u201332 (2006)","journal-title":"Algorithmica"},{"key":"128_CR18","doi-asserted-by":"crossref","unstructured":"Estrella-Balderrama, A., Fowler, J.J., Kobourov, S.G.: On the characterization of level planar trees by minimal patterns. In: Eppstein, D., Gansner, E.R. (eds.) GD\u201909. LNCS, vol. 5849, pp. 69\u201380 (2010)","DOI":"10.1007\/978-3-642-11805-0_9"},{"key":"128_CR19","doi-asserted-by":"crossref","unstructured":"Feng, Q., Cohen, R.F., Eades, P.: Planarity for clustered graphs. In: Spirakis (ed.) European Symposium on Algorithms (ESA \u201995). LNCS, vol. 979, pp. 213\u2013226 (1995)","DOI":"10.1007\/3-540-60313-1_145"},{"key":"128_CR20","doi-asserted-by":"crossref","unstructured":"Forster, M., Bachmaier, C.: Clustered level planarity. In: van Emde Boas, P., Pokorn\u00fd, J., Bielikov\u00e1, M., Stuller, J. (eds.) SOFSEM \u201904. LNCS, vol. 2932, pp. 218\u2013228 (2004)","DOI":"10.1007\/978-3-540-24618-3_18"},{"key":"128_CR21","doi-asserted-by":"crossref","unstructured":"Fowler, J.J., Kobourov, S.G.: Minimum level nonplanar patterns for trees. In: Hong, S.H., Nishizeki, T., Quan, W. (eds.) GD\u201907. LNCS, vol. 4875, pp. 69\u201375 (2008)","DOI":"10.1007\/978-3-540-77537-9_10"},{"key":"128_CR22","unstructured":"Fulek, R.: Toward the Hanani-Tutte theorem for clustered graphs. CoRR abs\/1410.3022 (2014). http:\/\/arxiv.org\/abs\/1410.3022"},{"issue":"2","key":"128_CR23","doi-asserted-by":"crossref","first-page":"601","DOI":"10.1137\/S0097539794277123","volume":"31","author":"A Garg","year":"2001","unstructured":"Garg, A., Tamassia, R.: On the computational complexity of upward and rectilinear planarity testing. SIAM J. Comput. 31(2), 601\u2013625 (2001)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"128_CR24","doi-asserted-by":"crossref","first-page":"73","DOI":"10.7155\/jgaa.00160","volume":"12","author":"C Gutwenger","year":"2008","unstructured":"Gutwenger, C., Klein, K., Mutzel, P.: Planarity testing and optimal edge insertion with embedding constraints. J. Graph Algorithms Appl. 12(1), 73\u201395 (2008)","journal-title":"J. Graph Algorithms Appl."},{"issue":"1\u20133","key":"128_CR25","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/j.disc.2003.02.001","volume":"280","author":"P Healy","year":"2004","unstructured":"Healy, P., Kuusik, A., Leipert, S.: A characterization of level planar graphs. Discrete Math. 280(1\u20133), 51\u201363 (2004)","journal-title":"Discrete Math."},{"issue":"4","key":"128_CR26","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1145\/321850.321852","volume":"21","author":"JE Hopcroft","year":"1974","unstructured":"Hopcroft, J.E., Tarjan, R.E.: Efficient planarity testing. J. ACM 21(4), 549\u2013568 (1974)","journal-title":"J. ACM"},{"issue":"2","key":"128_CR27","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1137\/S0097539792235906","volume":"25","author":"MD Hutton","year":"1996","unstructured":"Hutton, M.D., Lubiw, A.: Upward planarity testing of single-source acyclic digraphs. SIAM J. Comput. 25(2), 291\u2013311 (1996)","journal-title":"SIAM J. Comput."},{"key":"128_CR28","doi-asserted-by":"crossref","unstructured":"Jel\u00ednek, V., Jel\u00ednkov\u00e1, E., Kratochv\u00edl, J., Lidick\u00fd, B.: Clustered planarity: Embedded clustered graphs with two-component clusters. In: GD \u201908. LNCS, vol. 5417, pp. 121\u2013132 (2009)","DOI":"10.1007\/978-3-642-00219-9_13"},{"issue":"4","key":"128_CR29","doi-asserted-by":"crossref","first-page":"466","DOI":"10.1016\/j.comgeo.2012.07.005","volume":"46","author":"V Jel\u00ednek","year":"2013","unstructured":"Jel\u00ednek, V., Kratochv\u00edl, J., Rutter, I.: A Kuratowski-type theorem for planarity of partially embedded graphs. Comput. Geom. 46(4), 466\u2013492 (2013)","journal-title":"Comput. Geom."},{"issue":"3","key":"128_CR30","doi-asserted-by":"crossref","first-page":"379","DOI":"10.7155\/jgaa.00192","volume":"13","author":"E Jel\u00ednkov\u00e1","year":"2009","unstructured":"Jel\u00ednkov\u00e1, E., K\u00e1ra, J., Kratochv\u00edl, J., Pergel, M., Such\u00fd, O., Vyskocil, T.: Clustered planarity: small clusters in cycles and Eulerian graphs. J. Graph Algorithms Appl. 13(3), 379\u2013422 (2009)","journal-title":"J. Graph Algorithms Appl."},{"key":"128_CR31","doi-asserted-by":"crossref","unstructured":"J\u00fcnger, M., Leipert, S., Mutzel, P.: Level planarity testing in linear time. In: Whitesides, S. (ed.) GD \u201998. LNCS, vol. 1547, pp. 224\u2013237 (1998)","DOI":"10.1007\/3-540-37623-2_17"},{"key":"128_CR32","doi-asserted-by":"crossref","unstructured":"Kowalik, L., Kurowski, M.: Short path queries in planar graphs in constant time. In: Larmore, L.L., Goemans, M.X. (eds.) Symposium on Theory of Computing. pp. 143\u2013148. ACM, New York (2003)","DOI":"10.1145\/780542.780565"},{"key":"128_CR33","unstructured":"Pach, J., Toth, G.: Monotone drawings of planar graphs. CoRR abs\/1101.0967 (2011). http:\/\/arxiv.org\/abs\/1101.0967"},{"issue":"4","key":"128_CR34","doi-asserted-by":"crossref","first-page":"367","DOI":"10.7155\/jgaa.00298","volume":"17","author":"M Schaefer","year":"2013","unstructured":"Schaefer, M.: Toward a theory of planarity: Hanani\u2013Tutte and planarity variants. J. Graph Algorithms Appl. 17(4), 367\u2013440 (2013)","journal-title":"J. Graph Algorithms Appl."},{"issue":"2","key":"128_CR35","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1109\/TSMC.1981.4308636","volume":"11","author":"K Sugiyama","year":"1981","unstructured":"Sugiyama, K., Tagawa, S., Toda, M.: Methods for visual understanding of hierarchical system structures. IEEE Trans. Syst. Man Cybern. 11(2), 109\u2013125 (1981)","journal-title":"IEEE Trans. Syst. Man Cybern."},{"issue":"3","key":"128_CR36","doi-asserted-by":"crossref","first-page":"421","DOI":"10.1137\/0216030","volume":"16","author":"R Tamassia","year":"1987","unstructured":"Tamassia, R.: On embedding a graph in the grid with the minimum number of bends. SIAM J. Comput. 16(3), 421\u2013444 (1987)","journal-title":"SIAM J. Comput."},{"volume-title":"Handbook of Graph Drawing and Visualization. Discrete Mathematics and Its Applications","year":"2013","key":"128_CR37","unstructured":"Tamassia, R. (ed.): Handbook of Graph Drawing and Visualization. Discrete Mathematics and Its Applications. CRC Press, Boca Raton, FL (2013)"},{"key":"128_CR38","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1137\/0201010","volume":"2","author":"RE Tarjan","year":"1972","unstructured":"Tarjan, R.E.: Depth first search and linear graph algorithms. SIAM J. Comput. 2, 146\u2013160 (1972)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"128_CR39","doi-asserted-by":"crossref","first-page":"245","DOI":"10.2307\/2371127","volume":"55","author":"H Whitney","year":"1933","unstructured":"Whitney, H.: 2-Isomorphic graphs. Am. J. Math. 55(1), 245\u2013254 (1933)","journal-title":"Am. J. Math."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0128-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0128-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0128-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0128-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T19:47:23Z","timestamp":1559072843000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0128-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,2,8]]},"references-count":39,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,4]]}},"alternative-id":["128"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0128-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2016,2,8]]}}}