Geodesic
Parameterized Complexity of 1-Planarity
Journal of Graph Algorithms and Applications, Special Issue on Graph Drawing Beyond Planarity , Tome 22 (2018) no. 1, pp. 23-49.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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.
DOI : 10.7155/jgaa.00457
Keywords: 1-planar graphs, split graphs, cographs, parameterized complexity, fixed-parameter tractability, kernelization, vertex cover number, tree-depth, cyclomatic number, graph bandwidth, NP-completeness 
@article{JGAA_2018_22_1_a2,
     author = {Michael Bannister and Sergio Cabello and David Eppstein},
     title = {Parameterized {Complexity} of {1-Planarity}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {23--49},
     publisher = {mathdoc},
     volume = {22},
     number = {1},
     year = {2018},
     doi = {10.7155/jgaa.00457},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00457/}
}
TY  - JOUR
AU  - Michael Bannister
AU  - Sergio Cabello
AU  - David Eppstein
TI  - Parameterized Complexity of 1-Planarity
JO  - Journal of Graph Algorithms and Applications
PY  - 2018
SP  - 23
EP  - 49
VL  - 22
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00457/
DO  - 10.7155/jgaa.00457
LA  - en
ID  - JGAA_2018_22_1_a2
ER  - 
%0 Journal Article
%A Michael Bannister
%A Sergio Cabello
%A David Eppstein
%T Parameterized Complexity of 1-Planarity
%J Journal of Graph Algorithms and Applications
%D 2018
%P 23-49
%V 22
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00457/
%R 10.7155/jgaa.00457
%G en
%F JGAA_2018_22_1_a2
Michael Bannister; Sergio Cabello; David Eppstein. Parameterized Complexity of 1-Planarity. Journal of Graph Algorithms and Applications, 
							Special Issue on Graph Drawing Beyond Planarity
					, Tome 22 (2018) no. 1, pp. 23-49. doi : 10.7155/jgaa.00457. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00457/

Cité par Sources :