{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:33:04Z","timestamp":1760441584025,"version":"3.40.3"},"publisher-location":"Cham","reference-count":30,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030358013"},{"type":"electronic","value":"9783030358020"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-35802-0_27","type":"book-chapter","created":{"date-parts":[[2019,11,27]],"date-time":"2019-11-27T23:02:50Z","timestamp":1574895770000},"page":"350-362","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A Note on Universal Point Sets for\u00a0Planar Graphs"],"prefix":"10.1007","author":[{"given":"Manfred","family":"Scheucher","sequence":"first","affiliation":[]},{"given":"Hendrik","family":"Schrezenmaier","sequence":"additional","affiliation":[]},{"given":"Raphael","family":"Steiner","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,11,28]]},"reference":[{"key":"27_CR1","unstructured":"IBM ILOG CPLEX Optimization Studio (2018). http:\/\/www.ibm.com\/products\/ilog-cplex-optimization-studio\/"},{"key":"27_CR2","unstructured":"Aichholzer, O.: Enumerating Order Types for Small Point Sets with Applications. http:\/\/www.ist.tugraz.at\/aichholzer\/research\/rp\/triangulations\/ordertypes\/"},{"issue":"3","key":"27_CR3","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1023\/A:1021231927255","volume":"19","author":"O Aichholzer","year":"2002","unstructured":"Aichholzer, O., Aurenhammer, F., Krasser, H.: Enumerating order types for small point sets with applications. Order 19(3), 265\u2013281 (2002). https:\/\/doi.org\/10.1023\/A:1021231927255","journal-title":"Order"},{"issue":"1","key":"27_CR4","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.comgeo.2005.07.005","volume":"36","author":"O Aichholzer","year":"2006","unstructured":"Aichholzer, O., Krasser, H.: Abstract order type extension and new results on the rectilinear crossing number. Comput. Geom.: Theory Appl. 36(1), 2\u201315 (2006). https:\/\/doi.org\/10.1016\/j.comgeo.2005.07.005","journal-title":"Comput. Geom.: Theory Appl."},{"key":"27_CR5","doi-asserted-by":"publisher","unstructured":"Angelini, P., Bruckdorfer, T., Di Battista, G., Kaufmann, M., Mchedlidze, T., Roselli, V., Squarcella, C.: Small universal point sets for k-outerplanar graphs. Discret. Comput. Geom. 1\u201341 (2018). https:\/\/doi.org\/10.1007\/s00454-018-0009-x","DOI":"10.1007\/s00454-018-0009-x"},{"key":"27_CR6","doi-asserted-by":"publisher","unstructured":"Balko, M., Fulek, R., Kyn\u010dl, J.: Crossing numbers and combinatorial characterization of monotone drawings of $$K_n$$. Discret. Comput. Geom. 53(1), 107\u2013143 (2015). https:\/\/doi.org\/10.1007\/s00454-014-9644-z","DOI":"10.1007\/s00454-014-9644-z"},{"issue":"2","key":"27_CR7","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":"27_CR8","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/j.endm.2008.06.005","volume":"31","author":"FJ Brandenburg","year":"2008","unstructured":"Brandenburg, F.J.: Drawing planar graphs on $$\\frac{8}{9}n^2$$ area. Electron. Notes Discret. Math. 31, 37\u201340 (2008). https:\/\/doi.org\/10.1016\/j.endm.2008.06.005","journal-title":"Electron. Notes Discret. Math."},{"issue":"2","key":"27_CR9","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/j.comgeo.2006.05.006","volume":"36","author":"P Brass","year":"2007","unstructured":"Brass, P., Cenek, E., Duncan, C.A., Efrat, A., Erten, C., Ismailescu, D.P., Kobourov, S.G., Lubiw, A., Mitchell, J.S.: On simultaneous planar graph embeddings. Comput. Geom. 36(2), 117\u2013130 (2007). https:\/\/doi.org\/10.1016\/j.comgeo.2006.05.006","journal-title":"Comput. Geom."},{"key":"27_CR10","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1016\/S1571-0653(05)80016-2","volume":"3","author":"G Brinkmann","year":"1999","unstructured":"Brinkmann, G., McKay, B.D.: Fast generation of some classes of planar graphs. Electron. Notes Discret. Math. 3, 28\u201331 (1999). https:\/\/doi.org\/10.1016\/S1571-0653(05)80016-2","journal-title":"Electron. Notes Discret. Math."},{"issue":"2","key":"27_CR11","doi-asserted-by":"publisher","first-page":"353","DOI":"10.7155\/jgaa.00132","volume":"10","author":"S 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). https:\/\/doi.org\/10.7155\/jgaa.00132","journal-title":"J. Graph Algorithms Appl."},{"issue":"1","key":"27_CR12","doi-asserted-by":"publisher","first-page":"529","DOI":"10.7155\/jgaa.00374","volume":"19","author":"J Cardinal","year":"2015","unstructured":"Cardinal, J., Hoffmann, M., Kusters, V.: On universal point sets for planar graphs. J. Graph Algorithms Appl. 19(1), 529\u2013547 (2015). https:\/\/doi.org\/10.7155\/jgaa.00374","journal-title":"J. Graph Algorithms Appl."},{"key":"27_CR13","doi-asserted-by":"crossref","unstructured":"Casta\u00f1eda, N., Urrutia, J.: Straight line embeddings of planar graphs on point sets. In: Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG 1996), pp. 312\u2013318 (1996). http:\/\/www.cccg.ca\/proceedings\/1996\/cccg1996_0052.pdf","DOI":"10.1515\/9780773591134-055"},{"issue":"4","key":"27_CR14","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. ACM SIGACT News 20(4), 83\u201386 (1989). https:\/\/doi.org\/10.1145\/74074.74088","journal-title":"ACM SIGACT News"},{"issue":"1","key":"27_CR15","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":"27_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"502","DOI":"10.1007\/978-3-540-24605-3_37","volume-title":"Theory and Applications of Satisfiability Testing","author":"N E\u00e9n","year":"2004","unstructured":"E\u00e9n, N., S\u00f6rensson, N.: An extensible SAT-solver. In: Giunchiglia, E., Tacchella, A. (eds.) SAT 2003. LNCS, vol. 2919, pp. 502\u2013518. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-24605-3_37"},{"key":"27_CR17","doi-asserted-by":"publisher","unstructured":"Felsner, S., Goodman, J.E.: Pseudoline arrangements. In: Toth, C.D., O\u2019Rourke, J., Goodman, J.E. (eds.) Handbook of Discrete and Computational Geometry, 3rd edn. CRC Press (2018). https:\/\/doi.org\/10.1201\/9781315119601","DOI":"10.1201\/9781315119601"},{"issue":"1","key":"27_CR18","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/S0166-218X(00)00232-8","volume":"109","author":"S Felsner","year":"2001","unstructured":"Felsner, S., Weil, H.: Sweeps, arrangements and signotopes. Discret. Appl. Math. 109(1), 67\u201394 (2001). https:\/\/doi.org\/10.1016\/S0166-218X(00)00232-8","journal-title":"Discret. Appl. Math."},{"key":"27_CR19","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":"27_CR20","unstructured":"Gurobi Optimization, LLC: Gurobi Optimizer (2018). http:\/\/www.gurobi.com"},{"key":"27_CR21","unstructured":"Krasser, H.: Order Types of Point Sets in the Plane. Ph.D. thesis, Institute for Theoretical Computer Science, Graz University of Technology, Austria (2003)"},{"key":"27_CR22","doi-asserted-by":"publisher","unstructured":"Kurowski, M.: A $$1.235n$$ lower bound on the number of points needed to draw all $$n$$-vertex planar graphs. Inf. Process. Lett. 92(2), 95\u201398 (2004). https:\/\/doi.org\/10.1016\/j.ipl.2004.06.009","DOI":"10.1016\/j.ipl.2004.06.009"},{"key":"27_CR23","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1016\/j.jsc.2013.09.003","volume":"60","author":"BD McKay","year":"2014","unstructured":"McKay, B.D., Piperno, A.: Practical graph isomorphism, II. J. Symb. Comput. 60, 94\u2013112 (2014). https:\/\/doi.org\/10.1016\/j.jsc.2013.09.003","journal-title":"J. Symb. Comput."},{"key":"27_CR24","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). https:\/\/doi.org\/10.2307\/2323956","journal-title":"Am. Math. Mon."},{"key":"27_CR25","unstructured":"Scheucher, M.: Webpage: Source Codes and Data for Universal Point Sets. http:\/\/page.math.tu-berlin.de\/~scheuch\/supplemental\/universal_sets"},{"key":"27_CR26","unstructured":"Scheucher, M.: On Order Types, Projective Classes, and Realizations. Bachelor\u2019s thesis, Graz University of Technology, Austria (2014). http:\/\/www.math.tu-berlin.de\/~scheuch\/publ\/bachelors_thesis_tm_2014.pdf"},{"key":"27_CR27","doi-asserted-by":"crossref","unstructured":"Scheucher, M., Schrezenmaier, H., Steiner, R.: A Note On Universal Point Sets for Planar Graphs. arXiv:1811.06482 (2018)","DOI":"10.1007\/978-3-030-35802-0_27"},{"key":"27_CR28","unstructured":"Schnyder, W.: Embedding planar graphs on the grid. In: Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 138\u2013148. Society for Industrial and Applied Mathematics (1990)"},{"key":"27_CR29","unstructured":"Stein, W.A., et al.: Sage Mathematics Software (Version 8.1). The Sage Development Team (2018). http:\/\/www.sagemath.org"},{"key":"27_CR30","unstructured":"Stein, W.A., et al.: Sage Reference Manual: Graph Theory (Release 8.1) (2018). http:\/\/doc.sagemath.org\/pdf\/en\/reference\/number_fields\/number_fields.pdf"}],"container-title":["Lecture Notes in Computer Science","Graph Drawing and Network Visualization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-35802-0_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,28]],"date-time":"2023-11-28T01:04:54Z","timestamp":1701133494000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-35802-0_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030358013","9783030358020"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-35802-0_27","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":"28 November 2019","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":"Prague","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Czech Republic","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":"17 September 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20 September 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"gd2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/kam.mff.cuni.cz\/gd2019\/","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":"113","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":"34","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":"8","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":"30% - 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.11","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":"12.55","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)"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}