{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,2]],"date-time":"2026-11-02T21:12:45Z","timestamp":1793653965430,"version":"4.5.1"},"publisher-location":"Singapore","reference-count":42,"publisher":"Springer Singapore","isbn-type":[{"value":"9789811565328","type":"print"},{"value":"9789811565335","type":"electronic"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"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":[[2020]]},"DOI":"10.1007\/978-981-15-6533-5_1","type":"book-chapter","created":{"date-parts":[[2020,9,30]],"date-time":"2020-09-30T13:06:26Z","timestamp":1601471186000},"page":"1-9","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Beyond Planar Graphs: Introduction"],"prefix":"10.1007","author":[{"given":"Seok-Hee","family":"Hong","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,10,1]]},"reference":[{"key":"1_CR1","doi-asserted-by":"publisher","unstructured":"Ackerman, E.: On the maximum number of edges in topological graphs with no four pairwise crossing edges. Discret. Comput. Geom. 41(3), 365\u2013375 (2009). \nhttps:\/\/doi.org\/10.1007\/s00454-009-9143-9","DOI":"10.1007\/s00454-009-9143-9"},{"key":"1_CR2","doi-asserted-by":"publisher","unstructured":"Agarwal, P.K., Aronov, B., Pach, J., Pollack, R., Sharir, M.: Quasi-planar graphs have a linear number of edges. Combinatorica 17(1), 1\u20139 (1997). \nhttps:\/\/doi.org\/10.1007\/BF01196127","DOI":"10.1007\/BF01196127"},{"key":"1_CR3","doi-asserted-by":"publisher","unstructured":"Angelini, P., Bekos, M.A., Brandenburg, F.J., Da Lozzo, G., Di Battista, G., Didimo, W., Hoffmann, M., Liotta, G., Montecchiani, F., Rutter, I., T\u00f3th, C.D.: Simple k-planar graphs are simple (k839+82391)-quasiplanar. J. Comb. Theory, Ser. B 142, 1\u201335 (2020). \nhttps:\/\/doi.org\/10.1016\/j.jctb.2019.08.006","DOI":"10.1016\/j.jctb.2019.08.006"},{"key":"1_CR4","doi-asserted-by":"publisher","unstructured":"Argyriou, E.N., Bekos, M.A., Symvonis, A.: The straight-line RAC drawing problem is np-hard. J. Graph Algorithms Appl. 16(2), 569\u2013597 (2012). \nhttps:\/\/doi.org\/10.7155\/jgaa.00274","DOI":"10.7155\/jgaa.00274"},{"key":"1_CR5","doi-asserted-by":"publisher","unstructured":"Auer, C., Bachmaier, C., Brandenburg, F.J., Glei\u00dfner, A., Hanauer, K., Neuwirth, D., Reislhuber, J.: Outer 1-planar graphs. Algorithmica 74(4), 1293\u20131320 (2016). \nhttps:\/\/doi.org\/10.1007\/s00453-015-0002-1","DOI":"10.1007\/s00453-015-0002-1"},{"key":"1_CR6","doi-asserted-by":"publisher","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). \nhttps:\/\/doi.org\/10.7155\/jgaa.00347","DOI":"10.7155\/jgaa.00347"},{"key":"1_CR7","doi-asserted-by":"publisher","unstructured":"Bae, S.W., Baffier, J., Chun, J., Eades, P., Eickmeyer, K., Grilli, L., Hong, S., Korman, M., Montecchiani, F., Rutter, I., T\u00f3th, C.D.: Gap-planar graphs. Theor. Comput. Sci. 745, 36\u201352 (2018). \nhttps:\/\/doi.org\/10.1016\/j.tcs.2018.05.029","DOI":"10.1016\/j.tcs.2018.05.029"},{"key":"1_CR8","doi-asserted-by":"publisher","unstructured":"Bannister, M.J., Cabello, S., Eppstein, D.: Parameterized complexity of 1-planarity. J. Graph Algorithms Appl. 22(1), 23\u201349 (2018). \nhttps:\/\/doi.org\/10.7155\/jgaa.00457","DOI":"10.7155\/jgaa.00457"},{"key":"1_CR9","unstructured":"Battista, G.D., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall (1999)"},{"key":"1_CR10","doi-asserted-by":"publisher","unstructured":"Bekos, M.A., Cornelsen, S., Grilli, L., Hong, S., Kaufmann, M.: On the recognition of fan-planar and maximal outer-fan-planar graphs. Algorithmica 79(2), 401\u2013427 (2017). \nhttps:\/\/doi.org\/10.1007\/s00453-016-0200-5","DOI":"10.1007\/s00453-016-0200-5"},{"key":"1_CR11","doi-asserted-by":"publisher","unstructured":"Biedl, T.C., Liotta, G., Montecchiani, F.: Embedding-preserving rectangle visibility representations of nonplanar graphs. Discret. Comput. Geom. 60(2), 345\u2013380 (2018). \nhttps:\/\/doi.org\/10.1007\/s00454-017-9939-y","DOI":"10.1007\/s00454-017-9939-y"},{"key":"1_CR12","doi-asserted-by":"publisher","unstructured":"Binucci, C., Giacomo, E.D., Didimo, W., Montecchiani, F., Patrignani, M., Symvonis, A., Tollis, I.G.: Fan-planarity: properties and complexity. Theor. Comput. Sci. 589, 76\u201386 (2015). \nhttps:\/\/doi.org\/10.1016\/j.tcs.2015.04.020","DOI":"10.1016\/j.tcs.2015.04.020"},{"key":"1_CR13","unstructured":"Borodin, O.V.: Solution of the Ringel problem on vertex-face coloring of planar graphs and coloring of $$1$$-planar graphs. Metody Diskret. Analiz. 41, 12\u201326, 108 (1984)"},{"key":"1_CR14","doi-asserted-by":"publisher","unstructured":"Brandenburg, F.J.: Recognizing optimal 1-planar graphs in linear time. Algorithmica 80(1), 1\u201328 (2018). \nhttps:\/\/doi.org\/10.1007\/s00453-016-0226-8","DOI":"10.1007\/s00453-016-0226-8"},{"key":"1_CR15","doi-asserted-by":"publisher","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). \nhttps:\/\/doi.org\/10.1137\/120872310","DOI":"10.1137\/120872310"},{"key":"1_CR16","doi-asserted-by":"publisher","unstructured":"Chaplick, S., Kryven, M., Liotta, G., L\u00f6ffler, A., Wolff, A.: Beyond outerplanarity. In: F.\u00a0Frati, K.\u00a0Ma (eds.) Graph Drawing and Network Visualization - 25th International Symposium, GD 2017, Boston, MA, USA, September 25-27, 2017, Revised Selected Papers, Lecture Notes in Computer Science, vol. 10692, pp. 546\u2013559. Springer (2017). \nhttps:\/\/doi.org\/10.1007\/978-3-319-73915-1_42","DOI":"10.1007\/978-3-319-73915-1_42"},{"key":"1_CR17","doi-asserted-by":"publisher","unstructured":"Cheong, O., Har-Peled, S., Kim, H., Kim, H.: On the number of edges of fan-crossing free graphs. Algorithmica 73(4), 673\u2013695 (2015). \nhttps:\/\/doi.org\/10.1007\/s00453-014-9935-z","DOI":"10.1007\/s00453-014-9935-z"},{"key":"1_CR18","doi-asserted-by":"publisher","unstructured":"Dehkordi, H.R., Eades, P., Hong, S., Nguyen, Q.H.: Circular right-angle crossing drawings in linear time. Theor. Comput. Sci. 639, 26\u201341 (2016). \nhttps:\/\/doi.org\/10.1016\/j.tcs.2016.05.017","DOI":"10.1016\/j.tcs.2016.05.017"},{"key":"1_CR19","doi-asserted-by":"publisher","unstructured":"Didimo, W., Eades, P., Liotta, G.: Drawing graphs with right angle crossings. Theor. Comput. Sci. 412(39), 5156\u20135166 (2011). \nhttps:\/\/doi.org\/10.1016\/j.tcs.2011.05.025","DOI":"10.1016\/j.tcs.2011.05.025"},{"key":"1_CR20","doi-asserted-by":"publisher","unstructured":"Didimo, W., Liotta, G., Montecchiani, F.: A survey on graph drawing beyond planarity. ACM Comput. Surv. 52(1), 4:1\u20134:37 (2019). \nhttps:\/\/doi.org\/10.1145\/3301281","DOI":"10.1145\/3301281"},{"key":"1_CR21","doi-asserted-by":"publisher","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). \nhttps:\/\/doi.org\/10.1016\/j.tcs.2013.09.029","DOI":"10.1016\/j.tcs.2013.09.029"},{"key":"1_CR22","doi-asserted-by":"publisher","unstructured":"Eades, P., Hong, S., Liotta, G., Katoh, N., Poon, S.: Straight-line drawability of a planar graph plus an edge. In: F.\u00a0Dehne, J.\u00a0Sack, U.\u00a0Stege (eds.) Algorithms and Data Structures - 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings, Lecture Notes in Computer Science, vol. 9214, pp. 301\u2013313. Springer (2015). \nhttps:\/\/doi.org\/10.1007\/978-3-319-21840-3_25","DOI":"10.1007\/978-3-319-21840-3_25"},{"key":"1_CR23","doi-asserted-by":"publisher","unstructured":"Eades, P., Liotta, G.: Right angle crossing graphs and 1-planarity. Discret. Appl. Math. 161(7\u20138), 961\u2013969 (2013). \nhttps:\/\/doi.org\/10.1016\/j.dam.2012.11.019","DOI":"10.1016\/j.dam.2012.11.019"},{"issue":"7\u20138","key":"1_CR24","doi-asserted-by":"publisher","first-page":"854","DOI":"10.1016\/j.disc.2005.11.056","volume":"307","author":"I Fabrici","year":"2007","unstructured":"Fabrici, I., Madaras, T.: The structure of 1-planar graphs. Discrete Mathematics 307(7\u20138), 854\u2013865 (2007)","journal-title":"Discrete Mathematics"},{"key":"1_CR25","first-page":"229","volume":"11","author":"I F\u00e1ry","year":"1948","unstructured":"F\u00e1ry, I.: On straight line representations of planar graphs. Acta Sci. Math. Szeged 11, 229\u2013233 (1948)","journal-title":"Acta Sci. Math. Szeged"},{"key":"1_CR26","doi-asserted-by":"publisher","unstructured":"Fox, J., Pach, J., Suk, A.: The number of edges in k-quasi-planar graphs. SIAM J. Discrete Math. 27(1), 550\u2013561 (2013). \nhttps:\/\/doi.org\/10.1137\/110858586","DOI":"10.1137\/110858586"},{"key":"1_CR27","doi-asserted-by":"publisher","unstructured":"Giacomo, E.D., Didimo, W., Eades, P., Liotta, G.: 2-layer right angle crossing drawings. Algorithmica 68(4), 954\u2013997 (2014). \nhttps:\/\/doi.org\/10.1007\/s00453-012-9706-7","DOI":"10.1007\/s00453-012-9706-7"},{"key":"1_CR28","doi-asserted-by":"publisher","unstructured":"Giacomo, E.D., Eades, P., Liotta, G., Meijer, H., Montecchiani, F.: Polyline drawings with topological constraints. Theor. Comput. Sci. 809, 250\u2013264 (2020). \nhttps:\/\/doi.org\/10.1016\/j.tcs.2019.12.016","DOI":"10.1016\/j.tcs.2019.12.016"},{"key":"1_CR29","doi-asserted-by":"publisher","unstructured":"Grigoriev, A., Bodlaender, H.L.: Algorithms for graphs embeddable with few crossings per edge. Algorithmica 49(1), 1\u201311 (2007). \nhttps:\/\/doi.org\/10.1007\/s00453-007-0010-x","DOI":"10.1007\/s00453-007-0010-x"},{"key":"1_CR30","doi-asserted-by":"publisher","unstructured":"Hong, S., Eades, P., Katoh, N., Liotta, G., Schweitzer, P., Suzuki, Y.: A linear-time algorithm for testing outer-1-planarity. Algorithmica 72(4), 1033\u20131054 (2015). \nhttps:\/\/doi.org\/10.1007\/s00453-014-9890-8","DOI":"10.1007\/s00453-014-9890-8"},{"key":"1_CR31","doi-asserted-by":"publisher","unstructured":"Hong, S., Nagamochi, H.: Re-embedding a 1-plane graph into a straight-line drawing in linear time. In: Y.\u00a0Hu, M.\u00a0N\u00f6llenburg (eds.) Graph Drawing and Network Visualization - 24th International Symposium, GD 2016, Athens, Greece, September 19-21, 2016, Revised Selected Papers, Lecture Notes in Computer Science, vol. 9801, pp. 321\u2013334. Springer (2016). \nhttps:\/\/doi.org\/10.1007\/978-3-319-50106-2_25","DOI":"10.1007\/978-3-319-50106-2_25"},{"key":"1_CR32","doi-asserted-by":"publisher","unstructured":"Hong, S., Nagamochi, H.: A linear-time algorithm for testing full outer-2-planarity. Discret. Appl. Math. 255, 234\u2013257 (2019). \nhttps:\/\/doi.org\/10.1016\/j.dam.2018.08.018","DOI":"10.1016\/j.dam.2018.08.018"},{"key":"1_CR33","doi-asserted-by":"crossref","unstructured":"Hong, S.H., Eades, P., Liotta, G., Poon, S.H.: F\u00e1ry\u2019s theorem for 1-planar graphs. In: J.\u00a0Gudmundsson, J.\u00a0Mestre, T.\u00a0Viglas (eds.) Proceedings of COCOON 2012, Lecture Notes in Computer Science, vol. 7434, pp. 335\u2013346. Springer (2012)","DOI":"10.1007\/978-3-642-32241-9_29"},{"key":"1_CR34","doi-asserted-by":"publisher","unstructured":"Hud\u00e1k, D., Madaras, T., Suzuki, Y.: On properties of maximal 1-planar graphs. Discussiones Mathematicae Graph Theory 32(4), 737\u2013747 (2012). \nhttps:\/\/doi.org\/10.7151\/dmgt.1639","DOI":"10.7151\/dmgt.1639"},{"key":"1_CR35","unstructured":"Kaufmann, M., Ueckerdt, T.: The density of fan-planar graphs. CoRR (2014). \nhttp:\/\/arxiv.org\/abs\/1403.6184"},{"key":"1_CR36","doi-asserted-by":"publisher","unstructured":"Kobourov, S.G., Liotta, G., Montecchiani, F.: An annotated bibliography on 1-planarity. Comput. Sci. Rev. 25, 49\u201367 (2017). \nhttps:\/\/doi.org\/10.1016\/j.cosrev.2017.06.002","DOI":"10.1016\/j.cosrev.2017.06.002"},{"issue":"1","key":"1_CR37","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":"1_CR38","unstructured":"Nagamochi, H.: Straight-line drawability of embedded graph. Technical Report 2013\u2013005, Department of Applied Mathematics and Physics, Kyoto University, Japan (2013)"},{"key":"1_CR39","doi-asserted-by":"publisher","unstructured":"Nishizeki, T., Rahman, M.S.: Planar Graph Drawing, Lecture Notes Series on Computing, vol.\u00a012. World Scientific (2004). \nhttps:\/\/doi.org\/10.1142\/5648","DOI":"10.1142\/5648"},{"issue":"3","key":"1_CR40","doi-asserted-by":"publisher","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"},{"key":"1_CR41","doi-asserted-by":"publisher","unstructured":"Suzuki, Y.: Optimal 1-planar graphs which triangulate other surfaces. Discret. Math. 310(1), 6\u201311 (2010). \nhttps:\/\/doi.org\/10.1016\/j.disc.2009.07.016","DOI":"10.1016\/j.disc.2009.07.016"},{"issue":"3","key":"1_CR42","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"}],"container-title":["Beyond Planar Graphs"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-15-6533-5_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,30]],"date-time":"2020-09-30T13:27:12Z","timestamp":1601472432000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-981-15-6533-5_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9789811565328","9789811565335"],"references-count":42,"URL":"https:\/\/doi.org\/10.1007\/978-981-15-6533-5_1","relation":{},"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"1 October 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}