Geodesic
1-Planarity of Graphs with a Rotation System
Journal of Graph Algorithms and Applications, Tome 19 (2015) no. 1, pp. 67-86.

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

A graph is 1-planar if it can be drawn in the plane such that each edge is crossed at most once. 1-planarity is known NP-hard, even for graphs of bounded bandwidth, pathwidth, or treewidth, and for near-planar graphs in which an edge is added to a planar graph. On the other hand, there is a linear time 1-planarity testing algorithm for maximal 1-planar graphs with a given rotation system. In this work, we show that 1-planarity remains NP-hard even for 3-connected graphs with (or without) a rotation system. Moreover, the crossing number problem remains NP-hard for 3-connected 1-planar graphs with (or without) a rotation system.
DOI : 10.7155/jgaa.00347
Keywords: graph drawing, 1-planarity, rotation system, NP-hardness 
@article{JGAA_2015_19_1_a3,
     author = {Christopher Auer and Franz Brandenburg and Andreas Glei{\ss}ner and Josef Reislhuber},
     title = {1-Planarity of {Graphs} with a {Rotation} {System}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {67--86},
     publisher = {mathdoc},
     volume = {19},
     number = {1},
     year = {2015},
     doi = {10.7155/jgaa.00347},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00347/}
}
TY  - JOUR
AU  - Christopher Auer
AU  - Franz Brandenburg
AU  - Andreas Gleißner
AU  - Josef Reislhuber
TI  - 1-Planarity of Graphs with a Rotation System
JO  - Journal of Graph Algorithms and Applications
PY  - 2015
SP  - 67
EP  - 86
VL  - 19
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00347/
DO  - 10.7155/jgaa.00347
LA  - en
ID  - JGAA_2015_19_1_a3
ER  - 
%0 Journal Article
%A Christopher Auer
%A Franz Brandenburg
%A Andreas Gleißner
%A Josef Reislhuber
%T 1-Planarity of Graphs with a Rotation System
%J Journal of Graph Algorithms and Applications
%D 2015
%P 67-86
%V 19
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00347/
%R 10.7155/jgaa.00347
%G en
%F JGAA_2015_19_1_a3
Christopher Auer; Franz Brandenburg; Andreas Gleißner; Josef Reislhuber. 1-Planarity of Graphs with a Rotation System. Journal of Graph Algorithms and Applications, Tome 19 (2015) no. 1, pp. 67-86. doi : 10.7155/jgaa.00347. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00347/

Cité par Sources :