Parameterized Complexity of 1-Planarity
Journal of Graph Algorithms and Applications · 01.01.2018 · 22 (1) · 23-49
DOI: 10.7155/jgaa.00457 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Graph Algorithms and Applications, online erschienen am 01.01.2018. Verfasst von Michael Bannister und 2 weiteren Autor:innen. Die Arbeit wurde bisher 28-mal zitiert (Crossref). Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
We consider the problem of drawing graphs with at most one crossing per edge. These drawings, and the graphs that can be drawn in this way, are called $1$-planar. Finding $1$-planar drawings is known to be ${\mathsf{NP}}$-hard, but we prove that it is fixed-parameter tractable with respect to the vertex cover number, tree-depth, and cyclomatic number. Special cases of these algorithms provide polynomial-time recognition algorithms for $1$-planar split graphs and $1$-planar cographs. However, recognizing $1$-planar graphs remains ${\mathsf{NP}}$-complete for graphs of bounded bandwidth, pathwidth, or treewidth.
Zitieren
APA
Bannister, M., Cabello, S., & Eppstein, D. (2018). Parameterized Complexity of 1-Planarity. Journal of Graph Algorithms and Applications, 22(1), 23-49. https://doi.org/10.7155/jgaa.00457
Vancouver
Bannister M, Cabello S, Eppstein D. Parameterized Complexity of 1-Planarity. Journal of Graph Algorithms and Applications. 2018;22(1):23-49. doi:10.7155/jgaa.00457
BibTeX
@article{Bannister2018,
author = {Bannister, Michael and Cabello, Sergio and Eppstein, David},
title = {Parameterized Complexity of 1-Planarity},
journal = {Journal of Graph Algorithms and Applications},
year = {2018},
volume = {22},
number = {1},
pages = {23--49},
doi = {10.7155/jgaa.00457}
}
EUVIMED