ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 24 (2024) #P2.10
https://doi.org/10.26493/1855-3974.2763.1e6
(Also available at http://amc-journal.eu)
There is a unique crossing-minimal rectilinear
drawing of K18*
Bernardo M. Ábrego , Silvia Fernández–Merchant
Departament of Mathematics, California State University at Northridge,
CA, United States
Oswin Aichholzer
Institute for Software Technology, University of Technology, Graz, Austria
Jesús Leaños †
Academic Unit of Mathematics, Autonomous University of Zacatecas, Mexico
Gelasio Salazar
Institute of Physics, Autonomous University of San Luis Potosi, Mexico
Received 8 December 2021, accepted 15 June 2023, published online 14 February 2024
Abstract
We show that, up to order type isomorphism, there is a unique crossing-minimal recti-
linear drawing of K18. It is easily verified that this drawing does not contain any crossing-
minimal drawing of K17. Therefore this settles, in the negative, the following question
from Aichholzer and Krasser: is it true that, for every integer n ≥ 4, there exists a crossing-
minimal drawing of Kn that contains a crossing-minimal drawing of Kn−1?
Keywords: Rectilinear crossing number, complete graphs, k-edges.
Math. Subj. Class. (2020): 05C10, 05C60
*We thank an anonymous referee for carefully reading an earlier version of this paper, and providing several
insightful comments, corrections, and suggestions.
†Corresponding author.
E-mail addresses: bernardo.abrego@csun.edu (Bernardo M. Ábrego), silvia.fernandez@csun.edu (Silvia
Fernández–Merchant), oaich@ist.tugraz.at (Oswin Aichholzer), jleanos@uaz.edu.mx (Jesús Leaños),
gsalazar@ifisica.uaslp.mx (Gelasio Salazar)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
ISSN 1855-3966 (tiskana izd.), ISSN 1855-3974 (elektronska izd.)
ARS MATHEMATICA CONTEMPORANEA 24 (2024) #P2.10
https://doi.org/10.26493/1855-3974.2763.1e6
(Dostopno tudi na http://amc-journal.eu)
Obstaja ena sama ravnočrtna risba K18 z
minimalnim številom presečišč*
Bernardo M. Ábrego , Silvia Fernández–Merchant
Departament of Mathematics, California State University at Northridge,
CA, United States
Oswin Aichholzer
Institute for Software Technology, University of Technology, Graz, Austria
Jesús Leaños †
Academic Unit of Mathematics, Autonomous University of Zacatecas, Mexico
Gelasio Salazar
Institute of Physics, Autonomous University of San Luis Potosi, Mexico
Prejeto 8. decembra 2021, sprejeto 15. junija 2023, objavljeno na spletu 14. februarja 2024
Povzetek
Pokažemo, da je, do izomorfizma vrste reda natančno, ena sama ravnočrtna risba grafa
K18 z minimalnim številom presečišč. Lahko je preveriti, da ta risba ne vsebuje nobene
risbe grafa K17 z minimalnim številom presečišč. Zato to podaja negativen odgovor na
naslednje vprašanje, ki sta ga zastavila Aichholzer in Krasser: ali je res, da za vsako celo
število n ≥ 4 obstaja risba grafa Kn z minimalnim številom presečišč, ki vsebuje risbo
grafa Kn−1 z minimalnim številom presečišč?
Ključne besede: Ravnočrtno število presečišč, polni grafi, k-povezave.
Math. Subj. Class. (2020): 05C10, 05C60
*Zahvaljujemo se anonimnemu recenzentu, ker je skrbno prebral prejšnjo različico tega prispevka in podal več
pronicljivih komentarjev, popravkov in predlogov.
†Kontaktni avtor.
E-poštni naslovi: bernardo.abrego@csun.edu (Bernardo M. Ábrego), silvia.fernandez@csun.edu (Silvia
Fernández–Merchant), oaich@ist.tugraz.at (Oswin Aichholzer), jleanos@uaz.edu.mx (Jesús Leaños),
gsalazar@ifisica.uaslp.mx (Gelasio Salazar)
cb To delo je objavljeno pod licenco https://creativecommons.org/licenses/by/4.0/