On the maximum crossing number

Markus Chimani; Stefan Felsner; Stephen Kobourov; Torsten Ueckerdt; Pavel Valtr; Alexander Wolff

doi:10.1007/978-3-319-78825-8_6

On the maximum crossing number

Markus Chimani
, Stefan Felsner
, Stephen Kobourov
, Torsten Ueckerdt
, Pavel Valtr
, Alexander Wolff

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

1 Scopus citations

Abstract

Research about crossings is typically about minimization. In this paper, we consider maximizing the number of crossings over all possible ways to draw a given graph in the plane. Alpert et al. [Electron. J. Combin., 2009] conjectured that any graph has a convex straight-line drawing, that is, a drawing with vertices in convex position, that maximizes the number of edge crossings. We disprove this conjecture by constructing a planar graph on twelve vertices that allows a non-convex drawing with more crossings than any convex one. Bald et al. [Proc. COCOON, 2016] showed that it is NP-hard to compute the maximum number of crossings of a geometric graph and that the weighted geometric case is NP-hard to approximate. We strengthen these results by showing hardness of approximation even for the unweighted geometric case and prove that the unweighted topological case is NP-hard.

Original language	English (US)
Title of host publication	Combinatorial Algorithms - 28th International Workshop, IWOCA 2017, Revised Selected Papers
Editors	William F. Smyth, Ljiljana Brankovic, Joe Ryan
Publisher	Springer-Verlag
Pages	61-74
Number of pages	14
ISBN (Print)	9783319788241
DOIs	https://doi.org/10.1007/978-3-319-78825-8_6
State	Published - 2018
Event	28th International Workshop on Combinational Algorithms, IWOCA 2017 - Newcastle, NSW, Australia Duration: Jul 17 2017 → Jul 21 2017

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10765 LNCS

Other

Other	28th International Workshop on Combinational Algorithms, IWOCA 2017
Country/Territory	Australia
City	Newcastle, NSW
Period	7/17/17 → 7/21/17

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-319-78825-8_6

Cite this

Chimani, M., Felsner, S., Kobourov, S., Ueckerdt, T., Valtr, P., & Wolff, A. (2018). On the maximum crossing number. In W. F. Smyth, L. Brankovic, & J. Ryan (Eds.), Combinatorial Algorithms - 28th International Workshop, IWOCA 2017, Revised Selected Papers (pp. 61-74). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10765 LNCS). Springer-Verlag. https://doi.org/10.1007/978-3-319-78825-8_6

On the maximum crossing number. / Chimani, Markus; Felsner, Stefan; Kobourov, Stephen et al.
Combinatorial Algorithms - 28th International Workshop, IWOCA 2017, Revised Selected Papers. ed. / William F. Smyth; Ljiljana Brankovic; Joe Ryan. Springer-Verlag, 2018. p. 61-74 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10765 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Chimani, M, Felsner, S, Kobourov, S, Ueckerdt, T, Valtr, P & Wolff, A 2018, On the maximum crossing number. in WF Smyth, L Brankovic & J Ryan (eds), Combinatorial Algorithms - 28th International Workshop, IWOCA 2017, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10765 LNCS, Springer-Verlag, pp. 61-74, 28th International Workshop on Combinational Algorithms, IWOCA 2017, Newcastle, NSW, Australia, 7/17/17. https://doi.org/10.1007/978-3-319-78825-8_6

Chimani M, Felsner S, Kobourov S, Ueckerdt T, Valtr P, Wolff A. On the maximum crossing number. In Smyth WF, Brankovic L, Ryan J, editors, Combinatorial Algorithms - 28th International Workshop, IWOCA 2017, Revised Selected Papers. Springer-Verlag. 2018. p. 61-74. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-78825-8_6

Chimani, Markus ; Felsner, Stefan ; Kobourov, Stephen et al. / On the maximum crossing number. Combinatorial Algorithms - 28th International Workshop, IWOCA 2017, Revised Selected Papers. editor / William F. Smyth ; Ljiljana Brankovic ; Joe Ryan. Springer-Verlag, 2018. pp. 61-74 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{b7c0f5aa4a1b4e258082b0dd20068189,

title = "On the maximum crossing number",

abstract = "Research about crossings is typically about minimization. In this paper, we consider maximizing the number of crossings over all possible ways to draw a given graph in the plane. Alpert et al. [Electron. J. Combin., 2009] conjectured that any graph has a convex straight-line drawing, that is, a drawing with vertices in convex position, that maximizes the number of edge crossings. We disprove this conjecture by constructing a planar graph on twelve vertices that allows a non-convex drawing with more crossings than any convex one. Bald et al. [Proc. COCOON, 2016] showed that it is NP-hard to compute the maximum number of crossings of a geometric graph and that the weighted geometric case is NP-hard to approximate. We strengthen these results by showing hardness of approximation even for the unweighted geometric case and prove that the unweighted topological case is NP-hard.",

author = "Markus Chimani and Stefan Felsner and Stephen Kobourov and Torsten Ueckerdt and Pavel Valtr and Alexander Wolff",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG, part of Springer Nature 2018.; 28th International Workshop on Combinational Algorithms, IWOCA 2017 ; Conference date: 17-07-2017 Through 21-07-2017",

year = "2018",

doi = "10.1007/978-3-319-78825-8\_6",

language = "English (US)",

isbn = "9783319788241",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer-Verlag",

pages = "61--74",

editor = "Smyth, \{William F.\} and Ljiljana Brankovic and Joe Ryan",

booktitle = "Combinatorial Algorithms - 28th International Workshop, IWOCA 2017, Revised Selected Papers",

}

TY - GEN

T1 - On the maximum crossing number

AU - Chimani, Markus

AU - Felsner, Stefan

AU - Kobourov, Stephen

AU - Ueckerdt, Torsten

AU - Valtr, Pavel

AU - Wolff, Alexander

PY - 2018

Y1 - 2018

N2 - Research about crossings is typically about minimization. In this paper, we consider maximizing the number of crossings over all possible ways to draw a given graph in the plane. Alpert et al. [Electron. J. Combin., 2009] conjectured that any graph has a convex straight-line drawing, that is, a drawing with vertices in convex position, that maximizes the number of edge crossings. We disprove this conjecture by constructing a planar graph on twelve vertices that allows a non-convex drawing with more crossings than any convex one. Bald et al. [Proc. COCOON, 2016] showed that it is NP-hard to compute the maximum number of crossings of a geometric graph and that the weighted geometric case is NP-hard to approximate. We strengthen these results by showing hardness of approximation even for the unweighted geometric case and prove that the unweighted topological case is NP-hard.

AB - Research about crossings is typically about minimization. In this paper, we consider maximizing the number of crossings over all possible ways to draw a given graph in the plane. Alpert et al. [Electron. J. Combin., 2009] conjectured that any graph has a convex straight-line drawing, that is, a drawing with vertices in convex position, that maximizes the number of edge crossings. We disprove this conjecture by constructing a planar graph on twelve vertices that allows a non-convex drawing with more crossings than any convex one. Bald et al. [Proc. COCOON, 2016] showed that it is NP-hard to compute the maximum number of crossings of a geometric graph and that the weighted geometric case is NP-hard to approximate. We strengthen these results by showing hardness of approximation even for the unweighted geometric case and prove that the unweighted topological case is NP-hard.

UR - https://www.scopus.com/pages/publications/85046005203

UR - https://www.scopus.com/pages/publications/85046005203#tab=citedBy

U2 - 10.1007/978-3-319-78825-8_6

DO - 10.1007/978-3-319-78825-8_6

M3 - Conference contribution

SN - 9783319788241

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 61

EP - 74

BT - Combinatorial Algorithms - 28th International Workshop, IWOCA 2017, Revised Selected Papers

A2 - Smyth, William F.

A2 - Brankovic, Ljiljana

A2 - Ryan, Joe

PB - Springer-Verlag

T2 - 28th International Workshop on Combinational Algorithms, IWOCA 2017

Y2 - 17 July 2017 through 21 July 2017

ER -

On the maximum crossing number

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this