EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Parameterized Complexity of 1-Planarity

Michael Bannister, Sergio Cabello, David Eppstein

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →