{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T04:27:50Z","timestamp":1778732870117,"version":"3.51.4"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2019,5,11]],"date-time":"2019-05-11T00:00:00Z","timestamp":1557532800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,9]]},"DOI":"10.1007\/s00453-019-00585-6","type":"journal-article","created":{"date-parts":[[2019,5,11]],"date-time":"2019-05-11T14:58:38Z","timestamp":1557586718000},"page":"3464-3493","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["NodeTrix Planarity Testing with Small Clusters"],"prefix":"10.1007","volume":"81","author":[{"given":"Emilio","family":"Di Giacomo","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giuseppe","family":"Liotta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maurizio","family":"Patrignani","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ignaz","family":"Rutter","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9192-2067","authenticated-orcid":false,"given":"Alessandra","family":"Tappini","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,5,11]]},"reference":[{"issue":"4","key":"585_CR1","doi-asserted-by":"publisher","first-page":"731","DOI":"10.7155\/jgaa.00437","volume":"21","author":"P Angelini","year":"2017","unstructured":"Angelini, P., Da Lozzo, G., Di Battista, G., Frati, F., Patrignani, M., Rutter, I.: Intersection-link representations of graphs. J. Graph Algorithms Appl. 21(4), 731\u2013755 (2017). \n                    https:\/\/doi.org\/10.7155\/jgaa.00437","journal-title":"J. Graph Algorithms Appl."},{"issue":"3","key":"585_CR2","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/0020-0190(79)90002-4","volume":"8","author":"B Aspvall","year":"1979","unstructured":"Aspvall, B., Plass, M.F., Tarjan, R.E.: A linear-time algorithm for testing the truth of certain quantified Boolean formulas. Inf. Process. Lett. 8(3), 121\u2013123 (1979). \n                    https:\/\/doi.org\/10.1016\/0020-0190(79)90002-4","journal-title":"Inf. Process. Lett."},{"issue":"11","key":"585_CR3","doi-asserted-by":"publisher","first-page":"1587","DOI":"10.1109\/TVCG.2010.265","volume":"17","author":"V Batagelj","year":"2011","unstructured":"Batagelj, V., Brandenburg, F., Didimo, W., Liotta, G., Palladino, P., Patrignani, M.: Visual analysis of large graphs using (X, Y)-clustering and hybrid visualizations. IEEE Trans. Vis. Comput. Graph. 17(11), 1587\u20131598 (2011). \n                    https:\/\/doi.org\/10.1109\/TVCG.2010.265","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"issue":"6","key":"585_CR4","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1016\/j.comgeo.2015.02.002","volume":"48","author":"T Bl\u00e4sius","year":"2015","unstructured":"Bl\u00e4sius, T., Rutter, I.: Disconnectivity and relative positions in simultaneous embeddings. Comput. Geom. 48(6), 459\u2013478 (2015). \n                    https:\/\/doi.org\/10.1016\/j.comgeo.2015.02.002","journal-title":"Comput. Geom."},{"issue":"2","key":"585_CR5","doi-asserted-by":"publisher","first-page":"139","DOI":"10.7155\/jgaa.00461","volume":"22","author":"G Da Lozzo","year":"2018","unstructured":"Da Lozzo, G., Di Battista, G., Frati, F., Patrignani, M.: Computing nodetrix representations of clustered graphs. J. Graph Algorithms Appl. 22(2), 139\u2013176 (2018). \n                    https:\/\/doi.org\/10.7155\/jgaa.00461","journal-title":"J. Graph Algorithms Appl."},{"key":"585_CR6","volume-title":"Graph Drawing","author":"G Di Battista","year":"1999","unstructured":"Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing. Prentice Hall, Upper Saddle River, NJ (1999)"},{"issue":"5","key":"585_CR7","doi-asserted-by":"publisher","first-page":"956","DOI":"10.1137\/S0097539794280736","volume":"25","author":"G Di Battista","year":"1996","unstructured":"Di Battista, G., Tamassia, R.: On-line planarity testing. SIAM J. Comput. 25(5), 956\u2013997 (1996). \n                    https:\/\/doi.org\/10.1137\/S0097539794280736","journal-title":"SIAM J. Comput."},{"issue":"4","key":"585_CR8","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1007\/s00453-005-1185-7","volume":"45","author":"E Di Giacomo","year":"2006","unstructured":"Di Giacomo, E., Didimo, W., Liotta, G., Wismath, S.K.: Book embeddability of series-parallel digraphs. Algorithmica 45(4), 531\u2013547 (2006). \n                    https:\/\/doi.org\/10.1007\/s00453-005-1185-7","journal-title":"Algorithmica"},{"key":"585_CR9","doi-asserted-by":"publisher","unstructured":"Di Giacomo, E., Liotta, G., Patrignani, M., Tappini, A.: NodeTrix planarity testing with small clusters. In: Proc. 25th International Symposium on Graph Drawing and Network Visualization (GD \u201917), LNCS, vol. 10692, pp. 479\u2013491 (2018). \n                    https:\/\/doi.org\/10.1007\/978-3-319-73915-1_37","DOI":"10.1007\/978-3-319-73915-1_37"},{"key":"585_CR10","doi-asserted-by":"publisher","unstructured":"Di Giacomo, E., Liotta, G., Patrignani, M., Tappini, A.: Planar k-NodeTrix Graphs\u2014a new family of beyond planar graphs. In: Frati, F., Ma, K. (eds.) Proc. 25th International Symposium on Graph Drawing and Network Visualization (GD \u201917), LNCS, vol. 10692, pp. 609\u2013611 (2018). \n                    https:\/\/doi.org\/10.1007\/978-3-319-73915-1","DOI":"10.1007\/978-3-319-73915-1"},{"key":"585_CR11","doi-asserted-by":"publisher","unstructured":"Even, S., Itai, A., Shamir, A.: On the complexity of time table and multi-commodity flow problems. In: Proceedings of the 16th Annual Symposium on Foundations of Computer Science, pp. 184\u2013193. IEEE Computer Society (1975). \n                    https:\/\/doi.org\/10.1109\/SFCS.1975.21","DOI":"10.1109\/SFCS.1975.21"},{"issue":"1","key":"585_CR12","doi-asserted-by":"publisher","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). \n                    https:\/\/doi.org\/10.7155\/jgaa.00160","journal-title":"J. Graph Algorithms Appl."},{"key":"585_CR13","series-title":"Addison-Wesley Series in Mathematics","doi-asserted-by":"publisher","DOI":"10.21236\/AD0705364","volume-title":"Graph Theory","author":"F Harary","year":"1969","unstructured":"Harary, F.: Graph Theory. Addison-Wesley Series in Mathematics. Addison Wesley, Boston (1969)"},{"issue":"6","key":"585_CR14","doi-asserted-by":"publisher","first-page":"1302","DOI":"10.1109\/TVCG.2007.70582","volume":"13","author":"N Henry","year":"2007","unstructured":"Henry, N., Fekete, J., McGuffin, M.J.: NodeTrix: a hybrid visualization of social networks. IEEE Trans. Vis. Comput. Graph. 13(6), 1302\u20131309 (2007). \n                    https:\/\/doi.org\/10.1109\/TVCG.2007.70582","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"issue":"6","key":"585_CR15","doi-asserted-by":"publisher","first-page":"372","DOI":"10.1145\/362248.362272","volume":"16","author":"J Hopcroft","year":"1973","unstructured":"Hopcroft, J., Tarjan, R.: Algorithm 447: efficient algorithms for graph manipulation. Commun. ACM 16(6), 372\u2013378 (1973). \n                    https:\/\/doi.org\/10.1145\/362248.362272","journal-title":"Commun. ACM"},{"issue":"3","key":"585_CR16","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1137\/0202012","volume":"2","author":"J Hopcroft","year":"1973","unstructured":"Hopcroft, J., Tarjan, R.E.: Dividing a graph into triconnected components. SIAM J. Comput. 2(3), 135\u2013158 (1973). \n                    https:\/\/doi.org\/10.1137\/0202012","journal-title":"SIAM J. Comput."},{"issue":"2","key":"585_CR17","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1145\/49097.49099","volume":"19","author":"BME Moret","year":"1988","unstructured":"Moret, B.M.E.: Planar NAE3SAT is in P. SIGACT News 19(2), 51\u201354 (1988). \n                    https:\/\/doi.org\/10.1145\/49097.49099","journal-title":"SIGACT News"},{"key":"585_CR18","unstructured":"NodeTrix Representations: a proof-of-concept editor. \n                    http:\/\/www.dia.uniroma3.it\/~dalozzo\/projects\/matrix"},{"key":"585_CR19","doi-asserted-by":"publisher","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of the 10th Annual ACM Symposium on Theory of Computing, pp. 216\u2013226 (1978). \n                    https:\/\/doi.org\/10.1145\/800133.804350","DOI":"10.1145\/800133.804350"},{"issue":"3","key":"585_CR20","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1145\/322326.322328","volume":"29","author":"K Takamizawa","year":"1982","unstructured":"Takamizawa, K., Nishizeki, T., Saito, N.: Linear-time computability of combinatorial problems on series-parallel graphs. J. ACM 29(3), 623\u2013641 (1982)","journal-title":"J. ACM"},{"issue":"2","key":"585_CR21","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1137\/0211023","volume":"11","author":"J Valdes","year":"1982","unstructured":"Valdes, J., Tarjan, R.E., Lawler, E.L.: The recognition of series parallel digraphs. SIAM J. Comput. 11(2), 298\u2013313 (1982)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"585_CR22","doi-asserted-by":"publisher","first-page":"1570","DOI":"10.1137\/060667621","volume":"22","author":"X Zhou","year":"2008","unstructured":"Zhou, X., Nishizeki, T.: Orthogonal drawings of series-parallel graphs with minimum bends. SIAM J. Discrete Math. 22(4), 1570\u20131604 (2008). \n                    https:\/\/doi.org\/10.1137\/060667621","journal-title":"SIAM J. Discrete Math."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00585-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00585-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00585-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,9]],"date-time":"2020-05-09T23:12:02Z","timestamp":1589065922000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00585-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,5,11]]},"references-count":22,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2019,9]]}},"alternative-id":["585"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00585-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,5,11]]},"assertion":[{"value":"14 June 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 May 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 May 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}