Recognizing IC-Planar and NIC-Planar Graphs Franz Brandenburg Vol. 22, no. 2, pp. 239-271, 2018. Regular paper. 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. Submitted: October 2016. Reviewed: February 2017. Revised: August 2017. Accepted: April 2018. Final: April 2018. Published: May 2018. Communicated by Antonios Symvonis article (PDF) BibTeX