Minimal non-1-planar graphs Original Research Article

A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by no more than one other edge. A non-1-planar graph G is minimal if the graph image is 1-planar for every edge e of G. We prove that there are infinitely many minimal non-1-planar graphs (MN-graphs). It is known that every 6-vertex graph is 1-planar. We show that the graph image is the unique 7-vertex MN-graph.