More on the crossing number of Kn: Monotone drawings

Bernardo M. Ábrego; Oswin Aichholzer; Silvia Fernández-Merchant; Pedro Ramos; Gelasio Salazar

doi:10.1016/j.endm.2013.10.064

More on the crossing number of K_n: Monotone drawings

Bernardo M. Ábrego^*, Oswin Aichholzer, Silvia Fernández-Merchant, Pedro Ramos, Gelasio Salazar

^*Corresponding author for this work

Graz University of Technology (90000)

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

Abstract

The Harary-Hill conjecture states that the minimum number of crossings in a drawing of the complete graph K_n is Z(n):=14⌊n2⌋⌊n-12⌋⌊n-22⌋⌊n-32⌋. This conjecture was recently proved for 2-page book drawings of K_n. As an extension of this technique, we prove the conjecture for monotone drawings of K_n, that is, drawings where all vertices have different x-coordinates and the edges are x-monotone curves.

Original language	English
Pages (from-to)	411-414
Number of pages	4
Journal	Electronic Notes in Discrete Mathematics
Volume	44
DOIs	https://doi.org/10.1016/j.endm.2013.10.064
Publication status	Published - 5 Nov 2013

Keywords

Complete graph
Crossing number
K-edge
Monotone drawing
Topological drawing

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Fields of Expertise

Information, Communication & Computing

Treatment code (Nähere Zuordnung)

Basic - Fundamental (Grundlagenforschung)

Access to Document

10.1016/j.endm.2013.10.064

Cite this

@article{c55993fc373647f180134e1a1733deac,

title = "More on the crossing number of Kn: Monotone drawings",

abstract = "The Harary-Hill conjecture states that the minimum number of crossings in a drawing of the complete graph Kn is Z(n):=14⌊n2⌋⌊n-12⌋⌊n-22⌋⌊n-32⌋. This conjecture was recently proved for 2-page book drawings of Kn. As an extension of this technique, we prove the conjecture for monotone drawings of Kn, that is, drawings where all vertices have different x-coordinates and the edges are x-monotone curves.",

keywords = "Complete graph, Crossing number, K-edge, Monotone drawing, Topological drawing, Discrete and Computational Geometry",

author = "{\'A}brego, {Bernardo M.} and Oswin Aichholzer and Silvia Fern{\'a}ndez-Merchant and Pedro Ramos and Gelasio Salazar",

note = "Funding Information: 1Email: [email protected] 2 Partially supported by the ESF EUROCORES programme EuroGIGA, CRP ComPoSe, under grant FWF I648-N18. Email: [email protected] 3Email: [email protected] 4 Partially supported by MEC grant MTM2011-22792 and ESF EUROCORES programme EuroGIGA, CRP ComPoSe, grant EUI-EURC-2011-4306. Email: [email protected] 5 Supported by CONACYT grant 106432. Email: [email protected]",

year = "2013",

month = nov,

day = "5",

doi = "10.1016/j.endm.2013.10.064",

language = "English",

volume = "44",

pages = "411--414",

journal = "Electronic Notes in Discrete Mathematics ",

issn = "1571-0653",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - More on the crossing number of Kn

T2 - Monotone drawings

AU - Ábrego, Bernardo M.

AU - Aichholzer, Oswin

AU - Fernández-Merchant, Silvia

AU - Ramos, Pedro

AU - Salazar, Gelasio

N1 - Funding Information: 1Email: [email protected] 2 Partially supported by the ESF EUROCORES programme EuroGIGA, CRP ComPoSe, under grant FWF I648-N18. Email: [email protected] 3Email: [email protected] 4 Partially supported by MEC grant MTM2011-22792 and ESF EUROCORES programme EuroGIGA, CRP ComPoSe, grant EUI-EURC-2011-4306. Email: [email protected] 5 Supported by CONACYT grant 106432. Email: [email protected]

PY - 2013/11/5

Y1 - 2013/11/5

N2 - The Harary-Hill conjecture states that the minimum number of crossings in a drawing of the complete graph Kn is Z(n):=14⌊n2⌋⌊n-12⌋⌊n-22⌋⌊n-32⌋. This conjecture was recently proved for 2-page book drawings of Kn. As an extension of this technique, we prove the conjecture for monotone drawings of Kn, that is, drawings where all vertices have different x-coordinates and the edges are x-monotone curves.

AB - The Harary-Hill conjecture states that the minimum number of crossings in a drawing of the complete graph Kn is Z(n):=14⌊n2⌋⌊n-12⌋⌊n-22⌋⌊n-32⌋. This conjecture was recently proved for 2-page book drawings of Kn. As an extension of this technique, we prove the conjecture for monotone drawings of Kn, that is, drawings where all vertices have different x-coordinates and the edges are x-monotone curves.

KW - Complete graph

KW - Crossing number

KW - K-edge

KW - Monotone drawing

KW - Topological drawing

KW - Discrete and Computational Geometry

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

U2 - 10.1016/j.endm.2013.10.064

DO - 10.1016/j.endm.2013.10.064

M3 - Article

SN - 1571-0653

VL - 44

SP - 411

EP - 414

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

ER -