Optimal 1-planar graphs which triangulate other surfaces (Q1045136): Difference between revisions

A simple graph \(G\) is called \textit{1-planar} if it can be drawn on the sphere \(S^2\) such that each of its edges crosses at most another edge. If \(E(G)\) is the edge set and \(V(G)\) is the vertex set of a 1-planar graph \(G\), then the inequality \(| E(G) | \leq 4| V(G) | - 8\) holds. If equality holds, then \(G\) is called an \textit{optimal 1-planar} graph. The main theorem states that given an orientable closed surface \(F^2\), there is an optimal 1-planar graph which can be embedded on \(F^2\) as a triangulation. For nonorientable closed surfaces of genus at most 3, it is shown that there is no optimal 1-planar embedding as a triangulation. For higher genus, the problem is still open.