[{"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2002.02287"}],"issue":"3","date_created":"2021-03-28T22:01:41Z","author":[{"full_name":"Arroyo Guevara, Alan M","first_name":"Alan M","orcid":"0000-0003-2401-8670","last_name":"Arroyo Guevara","id":"3207FDC6-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Dan","last_name":"Mcquillan","full_name":"Mcquillan, Dan"},{"full_name":"Richter, R. Bruce","first_name":"R. Bruce","last_name":"Richter"},{"full_name":"Salazar, Gelasio","first_name":"Gelasio","last_name":"Salazar"},{"last_name":"Sullivan","first_name":"Matthew","full_name":"Sullivan, Matthew"}],"project":[{"_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships"}],"intvolume":"        97","acknowledgement":"We thank two reviewers for their corrections and suggestions on the original version of this\r\npaper. This project has received funding from NSERC Grant 50503-10940-500 and from the European Union’s Horizon 2020 research and innovation programme under the Marie SkłodowskaCurie grant agreement No 754411, IST, Klosterneuburg, Austria.","doi":"10.1002/jgt.22665","department":[{"_id":"UlWa"}],"scopus_import":"1","abstract":[{"lang":"eng","text":"Hill's Conjecture states that the crossing number  cr(𝐾𝑛)  of the complete graph  𝐾𝑛  in the plane (equivalently, the sphere) is  14⌊𝑛2⌋⌊𝑛−12⌋⌊𝑛−22⌋⌊𝑛−32⌋=𝑛4/64+𝑂(𝑛3) . Moon proved that the expected number of crossings in a spherical drawing in which the points are randomly distributed and joined by geodesics is precisely  𝑛4/64+𝑂(𝑛3) , thus matching asymptotically the conjectured value of  cr(𝐾𝑛) . Let  cr𝑃(𝐺)  denote the crossing number of a graph  𝐺  in the projective plane. Recently, Elkies proved that the expected number of crossings in a naturally defined random projective plane drawing of  𝐾𝑛  is  (𝑛4/8𝜋2)+𝑂(𝑛3) . In analogy with the relation of Moon's result to Hill's conjecture, Elkies asked if  lim𝑛→∞ cr𝑃(𝐾𝑛)/𝑛4=1/8𝜋2 . We construct drawings of  𝐾𝑛  in the projective plane that disprove this."}],"ec_funded":1,"publication_identifier":{"eissn":["1097-0118"],"issn":["0364-9024"]},"article_processing_charge":"No","_id":"9295","publication_status":"published","day":"23","external_id":{"isi":["000631693200001"],"arxiv":["2002.02287"]},"oa":1,"quality_controlled":"1","oa_version":"Preprint","title":"Drawings of complete graphs in the projective plane","status":"public","article_type":"original","citation":{"mla":"Arroyo Guevara, Alan M., et al. “Drawings of Complete Graphs in the Projective Plane.” <i>Journal of Graph Theory</i>, vol. 97, no. 3, Wiley, 2021, pp. 426–40, doi:<a href=\"https://doi.org/10.1002/jgt.22665\">10.1002/jgt.22665</a>.","short":"A.M. Arroyo Guevara, D. Mcquillan, R.B. Richter, G. Salazar, M. Sullivan, Journal of Graph Theory 97 (2021) 426–440.","ieee":"A. M. Arroyo Guevara, D. Mcquillan, R. B. Richter, G. Salazar, and M. Sullivan, “Drawings of complete graphs in the projective plane,” <i>Journal of Graph Theory</i>, vol. 97, no. 3. Wiley, pp. 426–440, 2021.","apa":"Arroyo Guevara, A. M., Mcquillan, D., Richter, R. B., Salazar, G., &#38; Sullivan, M. (2021). Drawings of complete graphs in the projective plane. <i>Journal of Graph Theory</i>. Wiley. <a href=\"https://doi.org/10.1002/jgt.22665\">https://doi.org/10.1002/jgt.22665</a>","ama":"Arroyo Guevara AM, Mcquillan D, Richter RB, Salazar G, Sullivan M. Drawings of complete graphs in the projective plane. <i>Journal of Graph Theory</i>. 2021;97(3):426-440. doi:<a href=\"https://doi.org/10.1002/jgt.22665\">10.1002/jgt.22665</a>","chicago":"Arroyo Guevara, Alan M, Dan Mcquillan, R. Bruce Richter, Gelasio Salazar, and Matthew Sullivan. “Drawings of Complete Graphs in the Projective Plane.” <i>Journal of Graph Theory</i>. Wiley, 2021. <a href=\"https://doi.org/10.1002/jgt.22665\">https://doi.org/10.1002/jgt.22665</a>.","ista":"Arroyo Guevara AM, Mcquillan D, Richter RB, Salazar G, Sullivan M. 2021. Drawings of complete graphs in the projective plane. Journal of Graph Theory. 97(3), 426–440."},"page":"426-440","year":"2021","month":"03","date_published":"2021-03-23T00:00:00Z","language":[{"iso":"eng"}],"date_updated":"2025-04-14T07:43:51Z","arxiv":1,"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","volume":97,"type":"journal_article","publication":"Journal of Graph Theory","publisher":"Wiley","isi":1},{"publication_status":"published","publication_identifier":{"issn":["0364-9024"]},"article_processing_charge":"No","_id":"5790","ec_funded":1,"abstract":[{"lang":"eng","text":"The partial representation extension problem is a recently introduced generalization of the recognition problem. A circle graph is an intersection graph of chords of a circle. We study the partial representation extension problem for circle graphs, where the input consists of a graph G and a partial representation R′ giving some predrawn chords that represent an induced subgraph of G. The question is whether one can extend R′ to a representation R of the entire graph G, that is, whether one can draw the remaining chords into a partially predrawn representation to obtain a representation of G. Our main result is an O(n3) time algorithm for partial representation extension of circle graphs, where n is the number of vertices. To show this, we describe the structure of all representations of a circle graph using split decomposition. This can be of independent interest."}],"scopus_import":"1","doi":"10.1002/jgt.22436","department":[{"_id":"UlWa"}],"project":[{"name":"International IST Postdoc Fellowship Programme","grant_number":"291734","call_identifier":"FP7","_id":"25681D80-B435-11E9-9278-68D0E5697425"}],"intvolume":"        91","author":[{"first_name":"Steven","last_name":"Chaplick","full_name":"Chaplick, Steven"},{"full_name":"Fulek, Radoslav","first_name":"Radoslav","last_name":"Fulek","orcid":"0000-0001-8485-1774","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Klavík","first_name":"Pavel","full_name":"Klavík, Pavel"}],"issue":"4","date_created":"2018-12-30T22:59:15Z","main_file_link":[{"url":"https://arxiv.org/abs/1309.2399","open_access":"1"}],"isi":1,"publisher":"Wiley","publication":"Journal of Graph Theory","type":"journal_article","volume":91,"arxiv":1,"user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","language":[{"iso":"eng"}],"date_published":"2019-08-01T00:00:00Z","date_updated":"2026-04-16T09:47:19Z","year":"2019","month":"08","page":"365-394","citation":{"short":"S. Chaplick, R. Fulek, P. Klavík, Journal of Graph Theory 91 (2019) 365–394.","mla":"Chaplick, Steven, et al. “Extending Partial Representations of Circle Graphs.” <i>Journal of Graph Theory</i>, vol. 91, no. 4, Wiley, 2019, pp. 365–94, doi:<a href=\"https://doi.org/10.1002/jgt.22436\">10.1002/jgt.22436</a>.","ieee":"S. Chaplick, R. Fulek, and P. Klavík, “Extending partial representations of circle graphs,” <i>Journal of Graph Theory</i>, vol. 91, no. 4. Wiley, pp. 365–394, 2019.","apa":"Chaplick, S., Fulek, R., &#38; Klavík, P. (2019). Extending partial representations of circle graphs. <i>Journal of Graph Theory</i>. Wiley. <a href=\"https://doi.org/10.1002/jgt.22436\">https://doi.org/10.1002/jgt.22436</a>","ama":"Chaplick S, Fulek R, Klavík P. Extending partial representations of circle graphs. <i>Journal of Graph Theory</i>. 2019;91(4):365-394. doi:<a href=\"https://doi.org/10.1002/jgt.22436\">10.1002/jgt.22436</a>","chicago":"Chaplick, Steven, Radoslav Fulek, and Pavel Klavík. “Extending Partial Representations of Circle Graphs.” <i>Journal of Graph Theory</i>. Wiley, 2019. <a href=\"https://doi.org/10.1002/jgt.22436\">https://doi.org/10.1002/jgt.22436</a>.","ista":"Chaplick S, Fulek R, Klavík P. 2019. Extending partial representations of circle graphs. Journal of Graph Theory. 91(4), 365–394."},"article_type":"original","status":"public","title":"Extending partial representations of circle graphs","oa_version":"Preprint","quality_controlled":"1","external_id":{"isi":["000485392800004"],"arxiv":["1309.2399"]},"day":"01","oa":1}]