{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:29:33Z","timestamp":1760441373072,"version":"3.40.3"},"publisher-location":"Cham","reference-count":34,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319501055"},{"type":"electronic","value":"9783319501062"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-50106-2_22","type":"book-chapter","created":{"date-parts":[[2016,12,7]],"date-time":"2016-12-07T15:22:42Z","timestamp":1481124162000},"page":"280-294","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Ortho-Polygon Visibility Representations of Embedded Graphs"],"prefix":"10.1007","author":[{"given":"Emilio","family":"Di Giacomo","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Walter","family":"Didimo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"William S.","family":"Evans","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giuseppe","family":"Liotta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Henk","family":"Meijer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fabrizio","family":"Montecchiani","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stephen K.","family":"Wismath","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,12,8]]},"reference":[{"key":"22_CR1","doi-asserted-by":"publisher","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. Discrete Appl. Math. 175, 104\u2013108 (2014)","journal-title":"Discrete Appl. Math."},{"key":"22_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/978-3-319-03841-4_8","volume-title":"Graph Drawing","author":"MJ Alam","year":"2013","unstructured":"Alam, M.J., Brandenburg, F.J., Kobourov, S.G.: Straight-line grid drawings of 3-connected 1-planar graphs. In: Wismath, S., Wolff, A. (eds.) GD 2013. LNCS, vol. 8242, pp. 83\u201394. Springer, Heidelberg (2013). doi: 10.1007\/978-3-319-03841-4_8"},{"key":"22_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/978-3-662-49192-8_10","volume-title":"SOFSEM 2016: Theory and Practice of Computer Science","author":"MJ Alam","year":"2016","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. LNCS, vol. 9587, pp. 121\u2013133. Springer, Heidelberg (2016). doi: 10.1007\/978-3-662-49192-8_10"},{"key":"22_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/978-3-642-40104-6_9","volume-title":"Algorithms and Data Structures","author":"MJ Bannister","year":"2013","unstructured":"Bannister, M.J., Cabello, S., Eppstein, D.: Parameterized complexity of 1-planarity. In: Dehne, F., Solis-Oba, R., Sack, J.-R. (eds.) WADS 2013. LNCS, vol. 8037, pp. 97\u2013108. Springer, Heidelberg (2013). doi: 10.1007\/978-3-642-40104-6_9"},{"key":"22_CR5","unstructured":"Biedl, T.C., Liotta, G., Montecchiani, F.: On visibility representations of non-planar graphs. In: Fekete, S.P., Lubiw, A. (eds) SoCG 2016, LIPIcs, vol. 51, pp. 19:1\u201319: 16. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2016). http:\/\/www.dagstuhl.de\/dagpub\/978-3-95977-009-5"},{"issue":"3","key":"22_CR6","doi-asserted-by":"publisher","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":"22_CR7","unstructured":"Brandenburg, F.J.: On 4-map graphs, 1-planar graphs, their recognition problem. CoRR, abs\/1509.03447 (2015). http:\/\/arxiv.org\/abs\/1509.03447"},{"issue":"5","key":"22_CR8","doi-asserted-by":"publisher","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":"22_CR9","doi-asserted-by":"publisher","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":"22_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. Electr. J. Comb. 20(2), P54 (2013)","journal-title":"Electr. J. Comb."},{"issue":"1","key":"22_CR11","doi-asserted-by":"publisher","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. Discrete Appl. Math. 75(1), 9\u201325 (1997)","journal-title":"Discrete Appl. Math."},{"key":"22_CR12","first-page":"571","volume-title":"Handbook of Graph Drawing and Visualization","author":"G Di Battista","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":"22_CR13","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 (1999)"},{"key":"22_CR14","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. ArXiv e-prints, abs\/1604.08797v2 (2016). http:\/\/arxiv.org\/abs\/1604.08797v2"},{"issue":"3","key":"22_CR15","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1016\/0012-365X(83)90128-0","volume":"46","author":"P Duchet","year":"1983","unstructured":"Duchet, P., Hamidoune, Y., Las Vergnas, M., Meyniel, H.: Representing a planar graph by vertical lines joining different levels. Discrete Math. 46(3), 319\u2013321 (1983)","journal-title":"Discrete Math."},{"key":"22_CR16","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/j.tcs.2013.09.029","volume":"513","author":"P Eades","year":"2013","unstructured":"Eades, P., Hong, S.-H., 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":"22_CR17","doi-asserted-by":"publisher","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":"22_CR18","doi-asserted-by":"publisher","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":"22_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/3-540-62495-3_49","volume-title":"Graph Drawing","author":"A Garg","year":"1997","unstructured":"Garg, A., Tamassia, R.: A new minimum cost flow algorithm with applications to graph drawing. In: North, S. (ed.) GD 1996. LNCS, vol. 1190, pp. 201\u2013216. Springer, Heidelberg (1997). doi: 10.1007\/3-540-62495-3_49"},{"issue":"3","key":"22_CR20","doi-asserted-by":"publisher","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":"2","key":"22_CR21","doi-asserted-by":"publisher","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."},{"issue":"1","key":"22_CR22","doi-asserted-by":"publisher","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":"22_CR23","unstructured":"Lenhart, W.J., Liotta, G., Montecchiani, F.: On partitioning the edges of 1-planar graphs. CoRR, abs\/1511.07303 (2015). http:\/\/arxiv.org\/abs\/1511.07303"},{"key":"22_CR24","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":"22_CR25","doi-asserted-by":"publisher","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, 343\u2013353 (1986)","journal-title":"Discrete Comput. Geom."},{"key":"22_CR26","unstructured":"Schnyder, W.: Embedding planar graphs on the grid. In: Johnson, D.S. (ed.), SODA 1990, pp. 138\u2013148. SIAM (1990)"},{"key":"22_CR27","doi-asserted-by":"crossref","unstructured":"Shermer, T.C.: On rectangle visibility graphs III. External visibility and complexity. In: Fiala, F., Kranakis, E., Sack, J.-R., (eds.) CCCG 1996, pp. 234\u2013239. Carleton University Press (1996)","DOI":"10.1515\/9780773591134-041"},{"key":"22_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1007\/3-540-36494-3_4","volume-title":"STACS 2003","author":"I Streinu","year":"2003","unstructured":"Streinu, I., Whitesides, S.: Rectangle visibility graphs: characterization, construction, and compaction. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol. 2607, pp. 26\u201337. Springer, Heidelberg (2003). doi: 10.1007\/3-540-36494-3_4"},{"issue":"4","key":"22_CR29","doi-asserted-by":"publisher","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":"22_CR30","doi-asserted-by":"publisher","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":"22_CR31","doi-asserted-by":"publisher","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(1), 321\u2013341 (1986)","journal-title":"Discrete Comput. Geom."},{"key":"22_CR32","unstructured":"Thomassen, C.: Plane representations of graphs. In: Progress in Graph Theory, pp. 43\u201369. AP (1984)"},{"issue":"3","key":"22_CR33","doi-asserted-by":"publisher","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":"22_CR34","doi-asserted-by":"crossref","unstructured":"Wismath, S.K.: Characterizing bar line-of-sight graphs. In: Rourke, J.O. (ed), SoCG 1985, pp. 147\u2013152. ACM (1985)","DOI":"10.1145\/323233.323253"}],"container-title":["Lecture Notes in Computer Science","Graph Drawing and Network Visualization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-50106-2_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,21]],"date-time":"2023-08-21T06:20:14Z","timestamp":1692598814000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-50106-2_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319501055","9783319501062"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-50106-2_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"8 December 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"GD","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Graph Drawing and Network Visualization","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Athens","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Greece","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2016","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 September 2016","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 September 2016","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"gd2016","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}