Recognizing IC-Planar and NIC-Planar Graphs

Abstract

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.