Home Issues About JGAA Instructions for Authors
 
DOI: 10.7155/jgaa.00466
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