{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,7]],"date-time":"2025-12-07T21:35:53Z","timestamp":1765143353854,"version":"3.40.3"},"publisher-location":"Cham","reference-count":30,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030108007"},{"type":"electronic","value":"9783030108014"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","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":[[2019]]},"DOI":"10.1007\/978-3-030-10801-4_21","type":"book-chapter","created":{"date-parts":[[2019,1,10]],"date-time":"2019-01-10T09:38:37Z","timestamp":1547113117000},"page":"260-271","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On Point Set Embeddings for k-Planar Graphs with Few Bends per Edge"],"prefix":"10.1007","author":[{"given":"Michael","family":"Kaufmann","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,1,11]]},"reference":[{"issue":"3","key":"21_CR1","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1016\/j.jcta.2006.08.002","volume":"114","author":"E Ackerman","year":"2007","unstructured":"Ackerman, E., Tardos, G.: On the maximum number of edges in quasi-planar graphs. J. Comb. Theor. Ser. A 114(3), 563\u2013571 (2007)","journal-title":"J. Comb. Theor. Ser. A"},{"issue":"1","key":"21_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01196127","volume":"17","author":"PK Agarwal","year":"1997","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)","journal-title":"Combinatorica"},{"issue":"2","key":"21_CR3","doi-asserted-by":"publisher","first-page":"430","DOI":"10.1007\/s00454-018-0009-x","volume":"60","author":"P Angelini","year":"2018","unstructured":"Angelini, P., et al.: Small universal point sets for k-outerplanar graphs. Discret. Comput. Geom. 60(2), 430\u2013470 (2018). https:\/\/doi.org\/10.1007\/s00454-018-0009-x","journal-title":"Discret. Comput. Geom."},{"issue":"2","key":"21_CR4","doi-asserted-by":"publisher","first-page":"177","DOI":"10.7155\/jgaa.00318","volume":"18","author":"MJ Bannister","year":"2014","unstructured":"Bannister, M.J., Cheng, Z., Devanny, W.E., Eppstein, D.: Superpatterns and universal point sets. J. Graph Algorithms Appl. 18(2), 177\u2013209 (2014). https:\/\/doi.org\/10.7155\/jgaa.00318","journal-title":"J. Graph Algorithms Appl."},{"key":"21_CR5","unstructured":"Bekos, M.A., Kaufmann, M., Raftopoulou, C.N.: On optimal 2- and 3-planar graphs. In: Aronov, B., Katz, M.J. (eds.) Symposium on Computational Geometry. LIPIcs, vol. 77, pp. 16:1\u201316:16. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2017)"},{"issue":"4","key":"21_CR6","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1007\/PL00009182","volume":"19","author":"TC Biedl","year":"1997","unstructured":"Biedl, T.C., Kant, G., Kaufmann, M.: On triangulating planar graphs under the four-connectivity constraint. Algorithmica 19(4), 427\u2013446 (1997). https:\/\/doi.org\/10.1007\/PL00009182","journal-title":"Algorithmica"},{"key":"21_CR7","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/3-540-63938-1_47","volume-title":"Graph Drawing","author":"Prosenjit Bose","year":"1997","unstructured":"Bose, P.: On embedding an outer-planar graph in a point set. In: Proceedings of Graph Drawing, 5th International Symposium, GD 1997, 18\u201320 September 1997, Rome, Italy, pp. 25\u201336 (1997). https:\/\/doi.org\/10.1007\/3-540-63938-1_47"},{"key":"21_CR8","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1007\/BFb0021791","volume-title":"Graph Drawing","author":"Prosenjit Bose","year":"1996","unstructured":"Bose, P., McAllister, M., Snoeyink, J.: Optimal algorithms to embed trees in a point set. In: Proceedings of Graph Drawing, Symposium on Graph Drawing, GD 1995, 20\u201322 September 1995, Passau, Germany, pp. 64\u201375 (1995). https:\/\/doi.org\/10.1007\/BFb0021791"},{"issue":"2","key":"21_CR9","doi-asserted-by":"publisher","first-page":"353","DOI":"10.7155\/jgaa.00132","volume":"10","author":"Sergio Cabello","year":"2006","unstructured":"Cabello, S.: Planar embeddability of the vertices of a graph using a fixed point set is NP-hard. J. Graph Algorithms Appl. 10(2), 353\u2013363 (2006). http:\/\/jgaa.info\/accepted\/2006\/Cabello2006.10.2.pdf","journal-title":"Journal of Graph Algorithms and Applications"},{"issue":"4","key":"21_CR10","doi-asserted-by":"publisher","first-page":"673","DOI":"10.1007\/s00453-014-9935-z","volume":"73","author":"O Cheong","year":"2015","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)","journal-title":"Algorithmica"},{"issue":"2","key":"21_CR11","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/0196-6774(89)90012-6","volume":"10","author":"N Chiba","year":"1989","unstructured":"Chiba, N., Nishizeki, T.: The hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs. J. Algorithms 10(2), 187\u2013211 (1989). https:\/\/doi.org\/10.1016\/0196-6774(89)90012-6","journal-title":"J. Algorithms"},{"issue":"4","key":"21_CR12","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1145\/74074.74088","volume":"20","author":"M Chrobak","year":"1989","unstructured":"Chrobak, M., Karloff, H.J.: A lower bound on the size of universal sets for planar graphs. SIGACT News 20(4), 83\u201386 (1989). https:\/\/doi.org\/10.1145\/74074.74088","journal-title":"SIGACT News"},{"issue":"39","key":"21_CR13","doi-asserted-by":"publisher","first-page":"5156","DOI":"10.1016\/j.tcs.2011.05.025","volume":"412","author":"W Didimo","year":"2011","unstructured":"Didimo, W., Eades, P., Liotta, G.: Drawing graphs with right angle crossings. Theor. Comput. Sci. 412(39), 5156\u20135166 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"21_CR14","unstructured":"Didimo, W., Liotta, G., Montecchiani, F.: A survey on graph drawing beyond planarity. CoRR abs\/1804.07257 (2018)"},{"key":"21_CR15","doi-asserted-by":"publisher","unstructured":"Feige, U.: Approximating the bandwidth via volume respecting embeddings (extended abstract). In: Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 23\u201326 May 1998, Dallas, Texas, USA, pp. 90\u201399 (1998). https:\/\/doi.org\/10.1145\/276698.276716","DOI":"10.1145\/276698.276716"},{"issue":"1","key":"21_CR16","doi-asserted-by":"publisher","first-page":"550","DOI":"10.1137\/110858586","volume":"27","author":"J Fox","year":"2013","unstructured":"Fox, J., Pach, J., Suk, A.: The number of edges in k-quasi-planar graphs. SIAM J. Discret. Math. 27(1), 550\u2013561 (2013)","journal-title":"SIAM J. Discret. Math."},{"issue":"1","key":"21_CR17","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). https:\/\/doi.org\/10.1007\/BF02122694","journal-title":"Combinatorica"},{"key":"21_CR18","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/j.jda.2014.12.005","volume":"30","author":"R Fulek","year":"2015","unstructured":"Fulek, R., T\u00f3th, C.D.: Universal point sets for planar three-trees. J. Discret. Algorithms 30, 101\u2013112 (2015). https:\/\/doi.org\/10.1016\/j.jda.2014.12.005","journal-title":"J. Discret. Algorithms"},{"key":"21_CR19","doi-asserted-by":"crossref","unstructured":"Hong, S., Tokuyama, T.: Algorithmics for beyond planar graphs. NII Shonan Meeting Seminar 089, 27 November\u20131 December 2016","DOI":"10.1007\/978-981-15-6533-5_1"},{"key":"21_CR20","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/BF02573994","volume":"11","author":"Y Ikebe","year":"1994","unstructured":"Ikebe, Y., Perles, M.A., Tamura, A., Tokunaga, S.: The rooted tree embedding problem into points in the plane. Discret. Comput. Geom. 11, 51\u201363 (1994). https:\/\/doi.org\/10.1007\/BF02573994","journal-title":"Discret. Comput. Geom."},{"key":"21_CR21","unstructured":"Kaufmann, M., Kobourov, S., Pach, J., Hong, S.: Beyond planar graphs: algorithmics and combinatorics. Dagstuhl Seminar 16452, 6\u201311 November 2016"},{"key":"21_CR22","unstructured":"Kaufmann, M., Ueckerdt, T.: The density of fan-planar graphs. CoRR abs\/1403.6184 (2014)"},{"issue":"1","key":"21_CR23","doi-asserted-by":"publisher","first-page":"115","DOI":"10.7155\/jgaa.00046","volume":"6","author":"Michael Kaufmann","year":"2002","unstructured":"Kaufmann, M., Wiese, R.: Embedding vertices at points: few bends suffice for planar graphs. J. Graph Algorithms Appl. 6(1), 115\u2013129 (2002). http:\/\/www.cs.brown.edu\/publications\/jgaa\/accepted\/2002\/KaufmannWiese2002.6.1.pdf","journal-title":"Journal of Graph Algorithms and Applications"},{"key":"21_CR24","volume-title":"Introduction to Parallel Algorithms and Architectures: Array, Trees, Hypercubes","author":"FT Leighton","year":"1992","unstructured":"Leighton, F.T.: Introduction to Parallel Algorithms and Architectures: Array, Trees, Hypercubes. Morgan Kaufmann Publishers Inc., San Francisco (1992)"},{"key":"21_CR25","unstructured":"Liotta, G.: Graph drawing beyond planarity: some results and open problems. SoCG Week, Invited talk, 4 July 2017"},{"issue":"4","key":"21_CR26","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1007\/s00454-006-1264-9","volume":"36","author":"J Pach","year":"2006","unstructured":"Pach, J., Radoi\u010di\u0107, R., Tardos, G., T\u00f3th, G.: Improving the crossing lemma by finding more crossings in sparse graphs. Discret. Comput. Geom. 36(4), 527\u2013552 (2006)","journal-title":"Discret. Comput. Geom."},{"issue":"3","key":"21_CR27","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":"21_CR28","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/3-540-37623-2_20","volume-title":"Graph Drawing","author":"J\u00e1nos Pach","year":"1998","unstructured":"Pach, J., Wenger, R.: Embedding planar graphs at fixed vertex locations. In: Proceedings of Graph Drawing, 6th International Symposium, GD 1998, August 1998, Montr\u00e9al, Canada, pp. 263\u2013274 (1998). https:\/\/doi.org\/10.1007\/3-540-37623-2_20"},{"key":"21_CR29","doi-asserted-by":"publisher","first-page":"165","DOI":"10.2307\/2323956","volume":"98","author":"J Pach","year":"1991","unstructured":"Pach, J., Gritzmann, P., Mohar, B., Pollack, R.: Embedding a planar triangulation with vertices at specified points. Am. Math. Mon. 98, 165\u2013166 (1991). Professor Pach\u2019s number: [065]","journal-title":"Am. Math. Mon."},{"key":"21_CR30","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. Hamb. 29, 107\u2013117 (1965)","journal-title":"Abh. Math. Sem. Univ. Hamb."}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2019: Theory and Practice of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-10801-4_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T11:16:47Z","timestamp":1709810207000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-10801-4_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030108007","9783030108014"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-10801-4_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"11 January 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SOFSEM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Current Trends in Theory and Practice of Informatics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Nov\u00fd Smokovec","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Slovakia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 January 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30 January 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"45","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sofsem2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/beda.dcs.fmph.uniba.sk\/sofsem2019\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"92","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"35","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"6","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"38% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.3","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}