{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,14]],"date-time":"2025-11-14T03:57:47Z","timestamp":1763092667941,"version":"3.40.3"},"publisher-location":"Singapore","reference-count":30,"publisher":"Springer Singapore","isbn-type":[{"type":"print","value":"9789811565328"},{"type":"electronic","value":"9789811565335"}],"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_5","type":"book-chapter","created":{"date-parts":[[2020,9,30]],"date-time":"2020-09-30T13:06:26Z","timestamp":1601471186000},"page":"69-87","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Algorithms for 1-Planar Graphs"],"prefix":"10.1007","author":[{"given":"Seok-Hee","family":"Hong","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,10,1]]},"reference":[{"key":"5_CR1","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"},{"issue":"1","key":"5_CR2","doi-asserted-by":"publisher","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). \nhttps:\/\/doi.org\/10.7155\/jgaa.00347","journal-title":"J. Graph Algorithms Appl."},{"issue":"1","key":"5_CR3","doi-asserted-by":"publisher","first-page":"23","DOI":"10.7155\/jgaa.00457","volume":"22","author":"MJ Bannister","year":"2018","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","journal-title":"J. Graph Algorithms Appl."},{"key":"5_CR4","unstructured":"Battista, G.D., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall (1999)"},{"issue":"4","key":"5_CR5","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1007\/BF01961541","volume":"15","author":"GD Battista","year":"1996","unstructured":"Battista, G.D., Tamassia, R.: On-line maintenance of triconnected components with spqr-trees. Algorithmica 15(4), 302\u2013318 (1996)","journal-title":"Algorithmica"},{"key":"5_CR6","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)"},{"issue":"1\u20133","key":"5_CR7","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/S0166-218X(00)00359-0","volume":"114","author":"OV Borodin","year":"2001","unstructured":"Borodin, O.V., Kostochka, A.V., Raspaud, A., Sopena, E.: Acyclic colouring of 1-planar graphs. Discret. Appl. Math. 114(1\u20133), 29\u201341 (2001)","journal-title":"Discret. Appl. Math."},{"issue":"5","key":"5_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). \nhttps:\/\/doi.org\/10.1137\/120872310","journal-title":"SIAM J. Comput."},{"key":"5_CR9","unstructured":"Chiba, N., Yamanouchi, T., Nishizeki, T.: Linear Time Algorithms for Convex Drawings of Planar Graphs. Progress in Graph Theory, pp. 153\u2013173 (1984)"},{"key":"5_CR10","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., 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","journal-title":"Theor. Comput. Sci."},{"key":"5_CR11","doi-asserted-by":"crossref","unstructured":"Eades, P., Hong, S., Liotta, G., Katoh, N., Poon, S.: Straight-line drawability of a planar graph plus an edge. In:\u00a0Dehne, F.,\u00a0Sack, J.,\u00a0Stege, U. (eds.) Algorithms and Data Structures - 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5\u20137, 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"},{"issue":"7\u20138","key":"5_CR12","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. Discret. Math. 307(7\u20138), 854\u2013865 (2007)","journal-title":"Discret. Math."},{"key":"5_CR13","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"},{"issue":"1","key":"5_CR14","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/BF02122694","volume":"10","author":"H de Fraysseix","year":"1990","unstructured":"de Fraysseix, H., Pach, J., Pollack, R.: How to draw a planar graph on a grid. Combinatorica 10(1), 41\u201351 (1990). \nhttps:\/\/doi.org\/10.1007\/BF02122694","journal-title":"Combinatorica"},{"issue":"1","key":"5_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-007-0010-x","volume":"49","author":"A Grigoriev","year":"2007","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","journal-title":"Algorithmica"},{"issue":"4","key":"5_CR16","doi-asserted-by":"publisher","first-page":"1033","DOI":"10.1007\/s00453-014-9890-8","volume":"72","author":"S Hong","year":"2015","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","journal-title":"Algorithmica"},{"issue":"2","key":"5_CR17","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/j.comgeo.2009.06.008","volume":"43","author":"S Hong","year":"2010","unstructured":"Hong, S., Nagamochi, H.: An algorithm for constructing star-shaped drawings of plane graphs. Comput. Geom. 43(2), 191\u2013206 (2010). \nhttps:\/\/doi.org\/10.1016\/j.comgeo.2009.06.008","journal-title":"Comput. Geom."},{"key":"5_CR18","doi-asserted-by":"crossref","unstructured":"Hong, S., Nagamochi, H.: Re-embedding a 1-plane graph into a straight-line drawing in linear time. In:\u00a0Hu, Y.,\u00a0N\u00f6llenburg, M., (eds.) Graph Drawing and Network Visualization - 24th International Symposium, GD 2016, Athens, Greece, September 19\u201321, 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":"5_CR19","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1016\/j.dam.2018.08.018","volume":"255","author":"S Hong","year":"2019","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","journal-title":"Discret. Appl. Math."},{"key":"5_CR20","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.,\u00a0Mestre, J.,\u00a0Viglas, T., (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"},{"issue":"4","key":"5_CR21","doi-asserted-by":"publisher","first-page":"737","DOI":"10.7151\/dmgt.1639","volume":"32","author":"D Hud\u00e1k","year":"2012","unstructured":"Hud\u00e1k, D., Madaras, T., Suzuki, Y.: On properties of maximal 1-planar graphs. Discuss. Math. Graph Theory 32(4), 737\u2013747 (2012). \nhttps:\/\/doi.org\/10.7151\/dmgt.1639","journal-title":"Discuss. Math. Graph Theory"},{"issue":"1","key":"5_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":"5_CR23","unstructured":"Nagamochi, H.: Straight-line drawability of embedded graphs, Technical Report 2013\u2013005. Kyoto University, Japan, Department of Applied Mathematics and Physics (2013)"},{"key":"5_CR24","doi-asserted-by":"crossref","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":"5_CR25","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":"5_CR26","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1007\/BF02996313","volume":"29","author":"G Ringel","year":"1965","unstructured":"Ringel, G.: Ein Sechsfarbenproblem auf der Kugel. Abh. Math. Sem. Univ. Hamburg 29, 107\u2013117 (1965)","journal-title":"Abh. Math. Sem. Univ. Hamburg"},{"issue":"1","key":"5_CR27","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1016\/j.disc.2009.07.016","volume":"310","author":"Y Suzuki","year":"2010","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","journal-title":"Discret. Math."},{"issue":"4","key":"5_CR28","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. Discret. Math. 24(4), 1527\u20131540 (2010). \nhttps:\/\/doi.org\/10.1137\/090746835","journal-title":"SIAM J. Discret. Math."},{"issue":"3","key":"5_CR29","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":"5_CR30","doi-asserted-by":"crossref","unstructured":"Zhang, X., Wu, J.L.: On edge colorings of 1-planar graphs. Inform. Process. Lett. 111(3), 124\u2013128 (2011). \nhttp:\/\/dx.doi.org\/10.1016\/j.ipl.2010.11.001","DOI":"10.1016\/j.ipl.2010.11.001"}],"container-title":["Beyond Planar Graphs"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-15-6533-5_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,30]],"date-time":"2020-09-30T13:34:48Z","timestamp":1601472888000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-981-15-6533-5_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9789811565328","9789811565335"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-981-15-6533-5_5","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"}}]}}