{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,22]],"date-time":"2025-12-22T04:24:24Z","timestamp":1766377464540,"version":"3.37.3"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2017,5,22]],"date-time":"2017-05-22T00:00:00Z","timestamp":1495411200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003407","name":"Ministero dell\u2019Istruzione, dell\u2019Universit\u00e0 e della Ricerca","doi-asserted-by":"publisher","award":["2012C4E3KT_001","2012C4E3KT_001"],"award-info":[{"award-number":["2012C4E3KT_001","2012C4E3KT_001"]}],"id":[{"id":"10.13039\/501100003407","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002790","name":"Canadian Network for Research and Innovation in Machining Technology, Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002790","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2018,8]]},"DOI":"10.1007\/s00453-017-0324-2","type":"journal-article","created":{"date-parts":[[2017,5,22]],"date-time":"2017-05-22T17:02:31Z","timestamp":1495472551000},"page":"2345-2383","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":18,"title":["Ortho-polygon Visibility Representations of Embedded Graphs"],"prefix":"10.1007","volume":"80","author":[{"given":"Emilio","family":"Di Giacomo","sequence":"first","affiliation":[]},{"given":"Walter","family":"Didimo","sequence":"additional","affiliation":[]},{"given":"William S.","family":"Evans","sequence":"additional","affiliation":[]},{"given":"Giuseppe","family":"Liotta","sequence":"additional","affiliation":[]},{"given":"Henk","family":"Meijer","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0543-8912","authenticated-orcid":false,"given":"Fabrizio","family":"Montecchiani","sequence":"additional","affiliation":[]},{"given":"Stephen K.","family":"Wismath","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,5,22]]},"reference":[{"key":"324_CR1","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1016\/j.dam.2014.05.025","volume":"175","author":"E Ackerman","year":"2014","unstructured":"Ackerman, E.: A note on 1-planar graphs. Discret. Appl. Math. 175, 104\u2013108 (2014)","journal-title":"Discret. Appl. Math."},{"key":"324_CR2","doi-asserted-by":"crossref","unstructured":"Alam, M.J., Brandenburg, F.J., Kobourov, S.G.: Straight-line grid drawings of 3-connected 1-planar graphs. In: Wismath, S.K., Wolff, A. (eds.) GD 2013, volume 8242 of LNCS, pp. 83\u201394. Springer, Berlin (2013)","DOI":"10.1007\/978-3-319-03841-4_8"},{"key":"324_CR3","doi-asserted-by":"crossref","unstructured":"Alam, M.J., Kobourov, S.G., Mondal, D.: Orthogonal layout with optimal face complexity. In: Freivalds, R.M., Engels, G., Catania, B. (eds.) SOFSEM 2016, volume 9587 of LNCS, pp. 121\u2013133. Springer, Berlin (2016)","DOI":"10.1007\/978-3-662-49192-8_10"},{"key":"324_CR4","doi-asserted-by":"crossref","unstructured":"Bannister, M.J., Cabello, S., Eppstein, D.: Parameterized complexity of 1-planarity. In: Dehne, F., Solis-Oba, R., Sack, J. (eds.) WADS 2013, volume 8037 of LNCS, pp. 97\u2013108. Springer, Berlin (2013)","DOI":"10.1007\/978-3-642-40104-6_9"},{"issue":"8","key":"324_CR5","doi-asserted-by":"crossref","first-page":"826","DOI":"10.1109\/12.868028","volume":"49","author":"P Bertolazzi","year":"2000","unstructured":"Bertolazzi, P., Di Battista, G., Didimo, W.: Computing orthogonal drawings with the minimum number of bends. IEEE Trans. Comput. 49(8), 826\u2013840 (2000)","journal-title":"IEEE Trans. Comput."},{"key":"324_CR6","unstructured":"Biedl, T.C., Liotta, G., Montecchiani, F.: On visibility representations of non-planar graphs. In: Fekete, S.P., Lubiw, A. (eds.) SoCG 2016, volume\u00a051 of LIPIcs, pp. 19:1\u201319:16. Schloss Dagstuhl\u2014Leibniz-Zentrum fuer Informatik (2016)"},{"issue":"3","key":"324_CR7","doi-asserted-by":"crossref","first-page":"421","DOI":"10.7155\/jgaa.00330","volume":"18","author":"FJ Brandenburg","year":"2014","unstructured":"Brandenburg, F.J.: 1-Visibility representations of 1-planar graphs. J. Graph Algorithms Appl. 18(3), 421\u2013438 (2014)","journal-title":"J. Graph Algorithms Appl."},{"issue":"5","key":"324_CR8","doi-asserted-by":"crossref","first-page":"1803","DOI":"10.1137\/120872310","volume":"42","author":"S Cabello","year":"2013","unstructured":"Cabello, S., Mohar, B.: Adding one edge to planar graphs makes crossing number and 1-planarity hard. SIAM J. Comput. 42(5), 1803\u20131829 (2013)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"324_CR9","doi-asserted-by":"crossref","first-page":"635","DOI":"10.7155\/jgaa.00265","volume":"16","author":"S Cornelsen","year":"2012","unstructured":"Cornelsen, S., Karrenbauer, A.: Accelerated bend minimization. J. Graph Algorithms Appl. 16(3), 635\u2013650 (2012)","journal-title":"J. Graph Algorithms Appl."},{"issue":"2","key":"324_CR10","doi-asserted-by":"crossref","first-page":"P54","DOI":"10.37236\/2392","volume":"20","author":"J Czap","year":"2013","unstructured":"Czap, J., Hud\u00e1k, D.: On drawings and decompositions of 1-planar graphs. Electron. J. Comb. 20(2), P54 (2013)","journal-title":"Electron. J. Comb."},{"issue":"1","key":"324_CR11","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1016\/S0166-218X(96)00029-7","volume":"75","author":"AM Dean","year":"1997","unstructured":"Dean, A.M., Hutchinson, J.P.: Rectangle-visibility representations of bipartite graphs. Discret. Appl. Math. 75(1), 9\u201325 (1997)","journal-title":"Discret. Appl. Math."},{"key":"324_CR12","first-page":"571","volume-title":"Handbook of Graph Drawing and Visualization","author":"G Battista Di","year":"2013","unstructured":"Di Battista, G., Didimo, W.: GDToolkit. In: Tamassia, R. (ed.) Handbook of Graph Drawing and Visualization, pp. 571\u2013597. CRC Press, Boca Raton (2013)"},{"key":"324_CR13","volume-title":"Graph Drawing","author":"G Battista Di","year":"1999","unstructured":"Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing. Prentice-Hall, Englewood Cliffs (1999)"},{"issue":"5","key":"324_CR14","doi-asserted-by":"crossref","first-page":"956","DOI":"10.1137\/S0097539794280736","volume":"25","author":"G Battista Di","year":"1996","unstructured":"Di Battista, G., Tamassia, R.: On-line planarity testing. SIAM J. Comput. 25(5), 956\u2013997 (1996)","journal-title":"SIAM J. Comput."},{"key":"324_CR15","doi-asserted-by":"crossref","unstructured":"Didimo, W., Liotta, G., Mehrabi, S., Montecchiani, F.: 1-Bend RAC drawings of 1-planar graphs. In: Hu, Y., N\u00f6llenburg, M. (eds.) GD 2016, volume 9801 of LNCS, pp. 335\u2013343. Springer, Berlin (2016)","DOI":"10.1007\/978-3-319-50106-2_26"},{"issue":"3","key":"324_CR16","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1016\/0012-365X(83)90128-0","volume":"46","author":"P Duchet","year":"1983","unstructured":"Duchet, P., Hamidoune, Y., Vergnas, M.L., Meyniel, H.: Representing a planar graph by vertical lines joining different levels. Discret. Math. 46(3), 319\u2013321 (1983)","journal-title":"Discret. Math."},{"key":"324_CR17","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/j.tcs.2013.09.029","volume":"513","author":"P Eades","year":"2013","unstructured":"Eades, P., Hong, S., Katoh, N., Liotta, G., Schweitzer, P., Suzuki, Y.: A linear time algorithm for testing maximal 1-planarity of graphs with a rotation system. Theor. Comput. Sci. 513, 65\u201376 (2013)","journal-title":"Theor. Comput. Sci."},{"issue":"7\u20138","key":"324_CR18","doi-asserted-by":"crossref","first-page":"961","DOI":"10.1016\/j.dam.2012.11.019","volume":"161","author":"P Eades","year":"2013","unstructured":"Eades, P., Liotta, G.: Right angle crossing graphs and 1-planarity. Discret. Appl. Math. 161(7\u20138), 961\u2013969 (2013)","journal-title":"Discret. Appl. Math."},{"issue":"5","key":"324_CR19","doi-asserted-by":"crossref","first-page":"721","DOI":"10.7155\/jgaa.00343","volume":"18","author":"WS Evans","year":"2014","unstructured":"Evans, W.S., Kaufmann, M., Lenhart, W., Mchedlidze, T., Wismath, S.K.: Bar 1-visibility graphs vs. other nearly planar graphs. J. Graph Algorithms Appl. 18(5), 721\u2013739 (2014)","journal-title":"J. Graph Algorithms Appl."},{"key":"324_CR20","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1016\/j.tcs.2016.06.045","volume":"645","author":"WS Evans","year":"2016","unstructured":"Evans, W.S., Liotta, G., Montecchiani, F.: Simultaneous visibility representations of plane $$st$$ s t -graphs using L-shapes. Theor. Comput. Sci. 645, 100\u2013111 (2016)","journal-title":"Theor. Comput. Sci."},{"key":"324_CR21","doi-asserted-by":"crossref","unstructured":"Garg, A., Tamassia, R.: A new minimum cost flow algorithm with applications to graph drawing. In: North, S.C. (ed.) GD \u201996, volume 1190 of LNCS, pp. 201\u2013216. Springer, Berlin (1996)","DOI":"10.1007\/3-540-62495-3_49"},{"issue":"4","key":"324_CR22","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1016\/j.orl.2008.02.003","volume":"36","author":"B Haeupler","year":"2008","unstructured":"Haeupler, B., Tarjan, R.E.: Finding a feasible flow in a strongly connected network. Oper. Res. Lett. 36(4), 397\u2013398 (2008)","journal-title":"Oper. Res. Lett."},{"issue":"3","key":"324_CR23","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/S0925-7721(99)00018-8","volume":"13","author":"JP Hutchinson","year":"1999","unstructured":"Hutchinson, J.P., Shermer, T.C., Vince, A.: On representations of some thickness-two graphs. Comput. Geom. 13(3), 161\u2013171 (1999)","journal-title":"Comput. Geom."},{"key":"324_CR24","doi-asserted-by":"crossref","unstructured":"Kant, G., Bodlaender, H.L.: Triangulating planar graphs while minimizing the maximum degree. In: Nurmi, O., Ukkonen, E. (eds.) SWAT 1992, volume 621 of LNCS, pp. 258\u2013271. Springer, Berlin (1992)","DOI":"10.1007\/3-540-55706-7_22"},{"issue":"2","key":"324_CR25","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/S0020-0190(97)00048-3","volume":"62","author":"G Kant","year":"1997","unstructured":"Kant, G., Liotta, G., Tamassia, R., Tollis, I.G.: Area requirement of visibility representations of trees. Inf. Process. Lett. 62(2), 81\u201388 (1997)","journal-title":"Inf. Process. Lett."},{"key":"324_CR26","doi-asserted-by":"crossref","unstructured":"Kobourov, S.G., Liotta, G., Montecchiani, F.: An annotated bibliography on 1-planarity. CoRR arXiv:1703.02261 (2017)","DOI":"10.1016\/j.cosrev.2017.06.002"},{"issue":"1","key":"324_CR27","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1002\/jgt.21630","volume":"72","author":"VP Korzhik","year":"2013","unstructured":"Korzhik, V.P., Mohar, B.: Minimal obstructions for 1-immersions and hardness of 1-planarity testing. J. Graph Theory 72(1), 30\u201371 (2013)","journal-title":"J. Graph Theory"},{"key":"324_CR28","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/j.tcs.2016.12.004","volume":"662","author":"WJ Lenhart","year":"2017","unstructured":"Lenhart, W.J., Liotta, G., Montecchiani, F.: On partitioning the edges of 1-plane graphs. Theor. Comput. Sci. 662, 59\u201365 (2017)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"324_CR29","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1016\/j.ipl.2015.11.011","volume":"116","author":"G Liotta","year":"2016","unstructured":"Liotta, G., Montecchiani, F.: L-visibility drawings of IC-planar graphs. Inf. Process. Lett. 116(3), 217\u2013222 (2016)","journal-title":"Inf. Process. Lett."},{"key":"324_CR30","unstructured":"Otten, R.H.J.M., Van Wijk, J.G.: Graph representations in interactive layout design. In: IEEE ISCSS, pp. 914\u2013918. IEEE (1978)"},{"key":"324_CR31","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1007\/BF02187706","volume":"1","author":"P Rosenstiehl","year":"1986","unstructured":"Rosenstiehl, P., Tarjan, R.E.: Rectilinear planar layouts and bipolar orientations of planar graphs. Discret. Comput. Geom. 1, 343\u2013353 (1986)","journal-title":"Discret. Comput. Geom."},{"key":"324_CR32","unstructured":"Schnyder, W.: Embedding planar graphs on the grid. In: Johnson, D.S. (ed.) SODA 1990, pp. 138\u2013148. SIAM (1990)"},{"key":"324_CR33","doi-asserted-by":"crossref","unstructured":"Shermer, T.C.: On rectangle visibility graphs. III. External visibility and complexity. In: Fiala, F., Kranakis, E., Sack, J. (eds.) CCCG 1996, pp. 234\u2013239. Carleton University Press, Kingston (1996)","DOI":"10.1515\/9780773591134-041"},{"key":"324_CR34","doi-asserted-by":"crossref","unstructured":"Streinu, I., Whitesides, S.: Rectangle visibility graphs: characterization, construction, and compaction. In: Alt, H., Habib, M. (eds.) STACS 2003, volume 2607 of LNCS, pp. 26\u201337. Springer, Berlin (2003)","DOI":"10.1007\/3-540-36494-3_4"},{"issue":"4","key":"324_CR35","doi-asserted-by":"crossref","first-page":"1527","DOI":"10.1137\/090746835","volume":"24","author":"Y Suzuki","year":"2010","unstructured":"Suzuki, Y.: Re-embeddings of maximum 1-planar graphs. SIAM J. Discret. Math. 24(4), 1527\u20131540 (2010)","journal-title":"SIAM J. Discret. Math."},{"issue":"3","key":"324_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. Comp. 16(3), 421\u2013444 (1987)","journal-title":"SIAM J. Comp."},{"issue":"1","key":"324_CR37","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1007\/BF02187705","volume":"1","author":"R Tamassia","year":"1986","unstructured":"Tamassia, R., Tollis, I.G.: A unified approach to visibility representations of planar graphs. Discret. Comput. Geom. 1(1), 321\u2013341 (1986)","journal-title":"Discret. Comput. Geom."},{"key":"324_CR38","unstructured":"Thomassen, C.: Plane representations of graphs. In: Progress in Graph Theory, pp. 43\u201369. AP (1984)"},{"issue":"3","key":"324_CR39","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1002\/jgt.3190120306","volume":"12","author":"C Thomassen","year":"1988","unstructured":"Thomassen, C.: Rectilinear drawings of graphs. J. Graph Theory 12(3), 335\u2013341 (1988)","journal-title":"J. Graph Theory"},{"key":"324_CR40","doi-asserted-by":"crossref","unstructured":"Wismath, S.K.: Characterizing bar line-of-sight graphs. In: O\u2019Rourke, J. (ed.) SoCG 1985, pp. 147\u2013152. ACM (1985)","DOI":"10.1145\/323233.323253"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-017-0324-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0324-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0324-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,23]],"date-time":"2023-08-23T17:43:36Z","timestamp":1692812616000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-017-0324-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,5,22]]},"references-count":40,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2018,8]]}},"alternative-id":["324"],"URL":"https:\/\/doi.org\/10.1007\/s00453-017-0324-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2017,5,22]]}}}