There is a unique crossing-minimal rectilinear drawing of K_18

Bernardo M. Ábrego; Silvia Fernández-Merchant; Oswin Aichholzer; Jesús Leaños; Gelasio Salazar

doi:10.26493/1855-3974.2763.1e6

There is a unique crossing-minimal rectilinear drawing of K_18

Bernardo M. Ábrego, Silvia Fernández-Merchant, Oswin Aichholzer, Jesús Leaños, Gelasio Salazar

Institut für Softwaretechnologie (7160)

Publikation: Beitrag in einer Fachzeitschrift › Artikel › Begutachtung

Abstract

We show that, up to order type isomorphism, there is a unique crossing-minimal rectilinear 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?

Originalsprache	englisch
Seitenumfang	29
Fachzeitschrift	Ars Mathematica Contemporanea
Jahrgang	24
Ausgabenummer	2
DOIs	https://doi.org/10.26493/1855-3974.2763.1e6
Publikationsstatus	Veröffentlicht - 2024

ASJC Scopus subject areas

Theoretische Informatik
Diskrete Mathematik und Kombinatorik
Geometrie und Topologie
Algebra und Zahlentheorie

Fields of Expertise

Information, Communication & Computing

Zugriff auf Dokument

10.26493/1855-3974.2763.1e6Lizenz: CC BY 4.0

Andere Dateien und Links

Verknüpfung zur Publikation in Scopus

Dieses zitieren

@article{6fe0590535b64518bb798ea9f3780059,

title = "There is a unique crossing-minimal rectilinear drawing of K_18",

abstract = "We show that, up to order type isomorphism, there is a unique crossing-minimal rectilinear 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 = "complete graphs, k-edges, Rectilinear crossing number",

author = "{\'A}brego, {Bernardo M.} and Silvia Fern{\'a}ndez-Merchant and Oswin Aichholzer and Jes{\'u}s Lea{\~n}os and Gelasio Salazar",

year = "2024",

doi = "10.26493/1855-3974.2763.1e6",

language = "English",

volume = "24",

journal = "Ars Mathematica Contemporanea",

issn = "1855-3966",

publisher = "DMFA Slovenije",

number = "2",

}

TY - JOUR

T1 - There is a unique crossing-minimal rectilinear drawing of K_18

AU - Ábrego, Bernardo M.

AU - Fernández-Merchant, Silvia

AU - Aichholzer, Oswin

AU - Leaños, Jesús

AU - Salazar, Gelasio

PY - 2024

Y1 - 2024

N2 - We show that, up to order type isomorphism, there is a unique crossing-minimal rectilinear 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?

AB - We show that, up to order type isomorphism, there is a unique crossing-minimal rectilinear 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?

KW - complete graphs

KW - k-edges

KW - Rectilinear crossing number

UR - http://www.scopus.com/inward/record.url?scp=85192743922&partnerID=8YFLogxK

U2 - 10.26493/1855-3974.2763.1e6

DO - 10.26493/1855-3974.2763.1e6

M3 - Article

SN - 1855-3966

VL - 24

JO - Ars Mathematica Contemporanea

JF - Ars Mathematica Contemporanea

IS - 2

ER -