Geodesic
Recognizing IC-Planar and NIC-Planar Graphs
Journal of Graph Algorithms and Applications, Tome 22 (2018) no. 2, pp. 239-271.

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

We prove that triangulated IC-planar graphs and triangulated $K_5$-free or $X4W$-free NIC-planar graphs can be recognized in cubic time. A graph is 1-planar if it can be drawn in the plane with at most one crossing per edge. A drawing is IC-planar if, in addition, each vertex is incident to at most one crossing edge and NIC-planar if two pairs of crossing edges share at most one vertex. In a triangulated drawing each face is a triangle. A graph is $K_5$-free ($X4W$-free) if it does not contain simple $K_5$ with a separating 3-cycle (extended 4-wheel graphs). In consequence, planar-maximal and maximal IC-planar graphs can be recognized in $O(n^5)$ time and maximum and optimal ones in $O(n^3)$ time. 
@article{JGAA_2018_22_2_a4,
     author = {Franz Brandenburg},
     title = {Recognizing {IC-Planar} and  {NIC-Planar} {Graphs}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {239--271},
     publisher = {mathdoc},
     volume = {22},
     number = {2},
     year = {2018},
     doi = {10.7155/jgaa.00466},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00466/}
}
TY  - JOUR
AU  - Franz Brandenburg
TI  - Recognizing IC-Planar and  NIC-Planar Graphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2018
SP  - 239
EP  - 271
VL  - 22
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00466/
DO  - 10.7155/jgaa.00466
LA  - en
ID  - JGAA_2018_22_2_a4
ER  - 
%0 Journal Article
%A Franz Brandenburg
%T Recognizing IC-Planar and  NIC-Planar Graphs
%J Journal of Graph Algorithms and Applications
%D 2018
%P 239-271
%V 22
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00466/
%R 10.7155/jgaa.00466
%G en
%F JGAA_2018_22_2_a4
Franz Brandenburg. Recognizing IC-Planar and  NIC-Planar Graphs. Journal of Graph Algorithms and Applications, Tome 22 (2018) no. 2, pp. 239-271. doi : 10.7155/jgaa.00466. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00466/

Cité par Sources :