{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:30:27Z","timestamp":1760441427752,"version":"3.37.3"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2017,10,4]],"date-time":"2017-10-04T00:00:00Z","timestamp":1507075200000},"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":["Discrete Comput Geom"],"published-print":{"date-parts":[[2018,9]]},"DOI":"10.1007\/s00454-017-9939-y","type":"journal-article","created":{"date-parts":[[2017,10,4]],"date-time":"2017-10-04T13:54:54Z","timestamp":1507125294000},"page":"345-380","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Embedding-Preserving Rectangle Visibility Representations of Nonplanar Graphs"],"prefix":"10.1007","volume":"60","author":[{"given":"Therese","family":"Biedl","sequence":"first","affiliation":[]},{"given":"Giuseppe","family":"Liotta","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0543-8912","authenticated-orcid":false,"given":"Fabrizio","family":"Montecchiani","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,10,4]]},"reference":[{"key":"9939_CR1","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: Graph Drawing. Lecture Notes in Computer Science, vol. 8242, pp. 83\u201394. Springer, Cham (2013)","DOI":"10.1007\/978-3-319-03841-4_8"},{"issue":"1","key":"9939_CR2","doi-asserted-by":"crossref","first-page":"67","DOI":"10.7155\/jgaa.00347","volume":"19","author":"C Auer","year":"2015","unstructured":"Auer, C., Brandenburg, F.J., Glei\u00dfner, A., Reislhuber, J.: 1-Planarity of graphs with a rotation system. J. Graph Algorithms Appl. 19(1), 67\u201386 (2015)","journal-title":"J. Graph Algorithms Appl."},{"key":"9939_CR3","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1016\/j.tcs.2017.05.039","volume":"689","author":"MA Bekos","year":"2017","unstructured":"Bekos, M.A., Didimo, W., Liotta, G., Mehrabi, S., Montecchiani, F.: On RAC drawings of 1-planar graphs. Theor. Comput. Sci. 689, 48\u201357 (2017)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"9939_CR4","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/S0020-0190(97)00207-X","volume":"65","author":"T Biedl","year":"1998","unstructured":"Biedl, T.: Relating bends and size in orthogonal graph drawings. Inform. Process. Lett. 65(2), 111\u2013115 (1998)","journal-title":"Inform. Process. Lett."},{"key":"9939_CR5","doi-asserted-by":"crossref","unstructured":"Biedl, T., Lubiw, A., Petrick, M., Spriggs, M.: Morphing orthogonal planar graph drawings. ACM Trans. Algorithms 9(4), Art. No. 29 (2013)","DOI":"10.1145\/2500118"},{"issue":"1","key":"9939_CR6","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/BF02941309","volume":"53","author":"R Bodendiek","year":"1983","unstructured":"Bodendiek, R., Schumacher, H., Wagner, K.: Bemerkungen zu einem Sechsfarbenproblem von G. Ringel. Abhandlungen aus dem Mathematischen Seminar der Universitaet Hamburg 53(1), 41\u201352 (1983)","journal-title":"Abhandlungen aus dem Mathematischen Seminar der Universitaet Hamburg"},{"issue":"3","key":"9939_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."},{"key":"9939_CR8","doi-asserted-by":"crossref","unstructured":"Brandenburg, F.J., Eppstein, D., Glei\u00dfner, A., Goodrich, M.T., Hanauer, K., Reislhuber, J.: On the density of maximal 1-planar graphs. In: Didimo, W., Patrignani, M. (eds.) Graph Drawing. Lecture Notes in Computer Science, vol. 7704, pp. 327\u2013338. Springer, Cham (2013)","DOI":"10.1007\/978-3-642-36763-2_29"},{"key":"9939_CR9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.tcs.2016.04.026","volume":"636","author":"FJ Brandenburg","year":"2016","unstructured":"Brandenburg, F.J., Didimo, W., Evans, W.S., Kindermann, P., Liotta, G., Montecchiani, F.: Recognizing and drawing IC-planar graphs. Theor. Comput. Sci. 636, 1\u201316 (2016)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"9939_CR10","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1007\/s00453-005-1184-8","volume":"45","author":"ZZ Chen","year":"2006","unstructured":"Chen, Z.Z., Grigni, M., Papadimitriou, C.H.: Recognizing hole-free 4-map graphs in cubic time. Algorithmica 45(2), 227\u2013262 (2006)","journal-title":"Algorithmica"},{"issue":"1","key":"9939_CR11","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1137\/0214017","volume":"14","author":"N Chiba","year":"1985","unstructured":"Chiba, N., Nishizeki, T.: Arboricity and subgraph listing algorithms. SIAM J. Comput. 14(1), 210\u2013223 (1985)","journal-title":"SIAM J. Comput."},{"key":"9939_CR12","doi-asserted-by":"crossref","unstructured":"Cohen, M.B., M\u0105dry, A., Sankowski, P., Vladu, A.: Negative-weight shortest paths and unit capacity minimum cost flow in $$\\widetilde{O}(m^{10\/7} \\log {W})$$ O ~ ( m 10 \/ 7 log W ) time (extended abstract). In: Klein, P.N. (ed.) Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201917), pp. 752\u2013771. SIAM, Philadelphia (2017)","DOI":"10.1137\/1.9781611974782.48"},{"key":"9939_CR13","doi-asserted-by":"crossref","unstructured":"Czap, J., Hud\u00e1k, D.: On drawings and decompositions of 1-planar graphs. Electron. J. Comb. 20(2), Art. No. 54 (2013)","DOI":"10.37236\/2392"},{"issue":"1","key":"9939_CR14","doi-asserted-by":"crossref","first-page":"45","DOI":"10.7155\/jgaa.00136","volume":"11","author":"AM Dean","year":"2007","unstructured":"Dean, A.M., Evans, W., Gethner, E., Laison, J.D., Safari, M.A., Trotter, W.T.: Bar $$k$$ k -visibility graphs. J. Graph Algorithms Appl. 11(1), 45\u201359 (2007)","journal-title":"J. Graph Algorithms Appl."},{"key":"9939_CR15","volume-title":"Graph Drawing: Algorithms for the Visualization of Graphs","author":"G Battista Di","year":"1999","unstructured":"Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall, Upper Saddle River (1999)"},{"key":"9939_CR16","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-017-0324-2","author":"E Giacomo Di","year":"2017","unstructured":"Di Giacomo, E., Didimo, W., Evans, W.S., Liotta, G., Meijer, H., Montecchiani, F., Wismath, S.K.: Ortho-polygon visibility representations of embedded graphs. Algorithmica (2017). doi: 10.1007\/s00453-017-0324-2","journal-title":"Algorithmica"},{"key":"9939_CR17","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1007\/978-1-4614-0110-0_10","volume-title":"Thirty Essays on Geometric Graph Theory","author":"W Didimo","year":"2013","unstructured":"Didimo, W., Liotta, G.: The crossing-angle resolution in graph drawing. In: Pach, J. (ed.) Thirty Essays on Geometric Graph Theory, pp. 167\u2013184. Springer, New York (2013)"},{"issue":"3","key":"9939_CR18","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. Discrete Math. 46(3), 319\u2013321 (1983)","journal-title":"Discrete Math."},{"issue":"7\u20138","key":"9939_CR19","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. Discrete Appl. Math. 161(7\u20138), 961\u2013969 (2013)","journal-title":"Discrete Appl. Math."},{"issue":"5","key":"9939_CR20","doi-asserted-by":"crossref","first-page":"721","DOI":"10.7155\/jgaa.00343","volume":"18","author":"W Evans","year":"2014","unstructured":"Evans, W., Kaufmann, M., Lenhart, W., Mchedlidze, T., Wismath, S.: Bar 1-visibility graphs and their relation to other nearly planar graphs. J. Graph Algorithms Appl. 18(5), 721\u2013739 (2014)","journal-title":"J. Graph Algorithms Appl."},{"key":"9939_CR21","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1007\/978-1-4614-0110-0_12","volume-title":"Thirty Essays on Geometric Graph Theory","author":"S Felsner","year":"2013","unstructured":"Felsner, S.: Rectangle and square representations of planar graphs. In: Pach, J. (ed.) Thirty Essays on Geometric Graph Theory, pp. 213\u2013248. Springer, New York (2013)"},{"issue":"7","key":"9939_CR22","doi-asserted-by":"crossref","first-page":"1870","DOI":"10.1016\/j.disc.2007.12.093","volume":"309","author":"\u00c9 Fusy","year":"2009","unstructured":"Fusy, \u00c9.: Transversal structures on triangulations: a combinatorial study and straight-line drawings. Discrete Math. 309(7), 1870\u20131894 (2009)","journal-title":"Discrete Math."},{"issue":"6","key":"9939_CR23","doi-asserted-by":"crossref","first-page":"1218","DOI":"10.1137\/0222072","volume":"22","author":"X He","year":"1993","unstructured":"He, X.: On finding the rectangular duals of planar triangular graphs. SIAM J. Comput. 22(6), 1218\u20131226 (1993)","journal-title":"SIAM J. Comput."},{"key":"9939_CR24","doi-asserted-by":"crossref","unstructured":"Hong, S.H., Eades, P., Liotta, G., Poon, S.H.: F\u00e1ry\u2019s theorem for 1-planar graphs. In: Gudmundsson, J., Mestre, J., Viglas, T. (eds.) Computing and Combinatorics. Lecture Notes in Computer Science, vol. 7434, pp. 335\u2013346. Springer, Berlin (2012)","DOI":"10.1007\/978-3-642-32241-9_29"},{"issue":"3","key":"9939_CR25","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."},{"issue":"3","key":"9939_CR26","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1142\/S0218195997000132","volume":"7","author":"G Kant","year":"1997","unstructured":"Kant, G.: A more compact visibility representation. Int. J. Comput. Geom. Appl. 7(3), 197\u2013210 (1997)","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"1","key":"9939_CR27","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1006\/inco.1997.2635","volume":"135","author":"G Kant","year":"1997","unstructured":"Kant, G., Bodlaender, H.L.: Triangulating planar graphs while minimizing the maximum degree. Inf. Comput. 135(1), 1\u201314 (1997)","journal-title":"Inf. Comput."},{"issue":"1\u20132","key":"9939_CR28","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1016\/S0304-3975(95)00257-X","volume":"172","author":"G Kant","year":"1997","unstructured":"Kant, G., He, X.: Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems. Theor. Comput. Sci. 172(1\u20132), 175\u2013193 (1997)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"9939_CR29","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":"9939_CR30","doi-asserted-by":"publisher","unstructured":"Kobourov, S.G., Liotta, G., Montecchiani, F.: An annotated bibliography on 1-planarity. Comput. Sci. Rev. doi: 10.1016\/j.cosrev.2017.06.002","DOI":"10.1016\/j.cosrev.2017.06.002"},{"issue":"7","key":"9939_CR31","doi-asserted-by":"crossref","first-page":"1319","DOI":"10.1016\/j.disc.2007.04.009","volume":"308","author":"VP Korzhik","year":"2008","unstructured":"Korzhik, V.P.: Minimal non-1-planar graphs. Discrete Math. 308(7), 1319\u20131327 (2008)","journal-title":"Discrete Math."},{"issue":"7","key":"9939_CR32","doi-asserted-by":"crossref","first-page":"1676","DOI":"10.1016\/j.ejc.2009.03.005","volume":"30","author":"J Kyn\u010dl","year":"2009","unstructured":"Kyn\u010dl, J.: Enumeration of simple complete topological graphs. Eur. J. Comb. 30(7), 1676\u20131685 (2009)","journal-title":"Eur. J. Comb."},{"issue":"3","key":"9939_CR33","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":"9939_CR34","doi-asserted-by":"crossref","unstructured":"Madry, A.: Computing maximum flow with augmenting electrical flows. In: Dinur, I. (ed.) IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS\u201916), pp. 593\u2013602. IEEE (2016)","DOI":"10.1109\/FOCS.2016.70"},{"key":"9939_CR35","unstructured":"Otten, R.H.J.M., Wijk, J.G.V.: Graph representations in interactive layout design. In: Proceedings of the IEEE International Symposium on Circuits and Systems (ISCSS\u201978), pp. 914\u2013918. IEEE (1978)"},{"issue":"3","key":"9939_CR36","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1007\/BF01215922","volume":"17","author":"J Pach","year":"1997","unstructured":"Pach, J., T\u00f3th, G.: Graphs drawn with few crossings per edge. Combinatorica 17(3), 427\u2013439 (1997)","journal-title":"Combinatorica"},{"issue":"4","key":"9939_CR37","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. Discrete Comput. Geom. 1(4), 343\u2013353 (1986)","journal-title":"Discrete Comput. Geom."},{"key":"9939_CR38","doi-asserted-by":"crossref","unstructured":"Shermer, T.C.: On rectangle visibility graphs. III. External visibility and complexity. In: Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG\u201996), pp. 234\u2013239. Carleton University Press, Ottawa (1996)","DOI":"10.1515\/9780773591134-041"},{"key":"9939_CR39","doi-asserted-by":"crossref","unstructured":"Streinu, I., Whitesides, S.: Rectangle visibility graphs: Characterization, construction, and compaction. In: Alt, H., Habib, M. (eds.) STACS 2003. Lecture Notes in Computer Science, vol. 2607, pp. 26\u201337. Springer, Berlin (2003)","DOI":"10.1007\/3-540-36494-3_4"},{"issue":"4","key":"9939_CR40","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. Discrete Math. 24(4), 1527\u20131540 (2010)","journal-title":"SIAM J. Discrete Math."},{"issue":"3","key":"9939_CR41","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."},{"issue":"4","key":"9939_CR42","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. Discrete Comput. Geom. 1(4), 321\u2013341 (1986)","journal-title":"Discrete Comput. Geom."},{"key":"9939_CR43","first-page":"43","volume-title":"Progress in Graph Theory","author":"C Thomassen","year":"1984","unstructured":"Thomassen, C.: Plane representations of graphs. In: Bondy, J.A., Murty, U.S.R. (eds.) Progress in Graph Theory, pp. 43\u201369. Academic Press, New York (1984)"},{"issue":"3","key":"9939_CR44","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":"9939_CR45","volume-title":"Computational Aspects of VLSI","author":"JD Ullman","year":"1984","unstructured":"Ullman, J.D.: Computational Aspects of VLSI. Computer Science Press, Rockville (1984)"},{"issue":"3","key":"9939_CR46","doi-asserted-by":"crossref","first-page":"336","DOI":"10.1112\/jlms\/s1-28.3.336","volume":"s1\u201328","author":"P Ungar","year":"1953","unstructured":"Ungar, P.: On diagrams representing maps. J. Lond. Math. Soc. s1\u201328(3), 336\u2013342 (1953)","journal-title":"J. Lond. Math. Soc."},{"key":"9939_CR47","doi-asserted-by":"crossref","unstructured":"Wismath, S.K.: Characterizing bar line-of-sight graphs. In: O\u2019Rourke, J. (ed.) Proceedings of the 1st Annual Symposium on Computational Geometry (SoCG\u201985), pp. 147\u2013152. ACM, New York (1985)","DOI":"10.1145\/323233.323253"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-017-9939-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-017-9939-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-017-9939-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,26]],"date-time":"2023-08-26T19:29:34Z","timestamp":1693078174000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-017-9939-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,10,4]]},"references-count":47,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,9]]}},"alternative-id":["9939"],"URL":"https:\/\/doi.org\/10.1007\/s00454-017-9939-y","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2017,10,4]]}}}