MathDBNP-hardness of testing IC-planarity and NIC-planarity
NP-hardness of testing IC-planarity and NIC-planarity
A graph is IC-planar if it has a plane drawing in which no two crossings share an endpoint, and NIC-planar if it has a plane drawing in which any two crossings share at most one endpoint. NP-hardness conjecture. Testing whether a graph is IC-planar and testing whether a graph is NIC-planar are NP-hard. The paper notes that testing 1-planarity is already known to be NP-hard, and proposes the analogous complexity classification for IC-planarity and NIC-planarity; the conjecture's resolution is not specified here.
Sources & referencesView supporting material
Primary source
Xin Zhang, “Drawing complete multipartite graphs on the plane with restrictions on crossings”, arXiv:1311.1994 (2013).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.