On the maximum crossing number
Autor(en): | Chimani, M. Felsner, S. Kobourov, S. Ueckerdt, T. Valtr, P. Wolff, A. |
Herausgeber: | Smyth, W.F. Brankovic, L. Ryan, J. |
Stichwörter: | Geometry, Convex drawings; Crossing number; Edge crossing; Geometric graphs; Hardness of approximation; Planar graph; Straight-line drawings; Weighted geometric, Graph theory | Erscheinungsdatum: | 2018 | Herausgeber: | Springer Verlag | Enthalten in: | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | Band: | 10765 LNCS | Startseite: | 61 | Seitenende: | 74 | Zusammenfassung: | 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. © Springer International Publishing AG, part of Springer Nature 2018. |
Beschreibung: | Conference of 28th International Workshop on Combinational Algorithms, IWOCA 2017 ; Conference Date: 17 July 2017 Through 21 July 2017; Conference Code:213049 |
ISBN: | 9783319788241 | ISSN: | 03029743 | DOI: | 10.1007/978-3-319-78825-8_6 | Externe URL: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-85046005203&doi=10.1007%2f978-3-319-78825-8_6&partnerID=40&md5=c02f95bf9b6a4a2f93734897436fcca6 |
Zur Langanzeige
Seitenaufrufe
2
Letzte Woche
0
0
Letzter Monat
0
0
geprüft am 06.06.2024