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

Institute of Software Engineering and Artificial Intelligence (7160)

Research output: Contribution to journal › Article › peer-review

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?

Original language	English
Number of pages	29
Journal	Ars Mathematica Contemporanea
Volume	24
Issue number	2
DOIs	https://doi.org/10.26493/1855-3974.2763.1e6
Publication status	Published - 2024

Keywords

complete graphs
k-edges
Rectilinear crossing number

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Geometry and Topology
Algebra and Number Theory

Fields of Expertise

Information, Communication & Computing

Access to Document

10.26493/1855-3974.2763.1e6Licence: CC BY 4.0

Cite this

@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 = "Society of Mathematicians, Physicists and Astronomers of Slovenia",

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 -

There is a unique crossing-minimal rectilinear drawing of K_18

Abstract

Keywords

ASJC Scopus subject areas

Fields of Expertise

Access to Document

Other files and links

Cite this