Every quadrangulation gives rise to an optimal 1-planar graph in this way, by adding the two diagonals to each of its quadrilateral faces.
Other than these infinite sets of examples, the only complete multipartite 1-planar graphs are K6, K1,1,1,6, K1,1,2,3, K2,2,2,2, K1,1,1,2,2, and their subgraphs.
[13] The problem is fixed-parameter tractable when parameterized by cyclomatic number or by tree-depth, so it may be solved in polynomial time when those parameters are bounded.
This drawing can be constructed in linear time from a 1-planar embedding of the graph.
[19] 1-planar graphs have bounded local treewidth, meaning that there is a (linear) function f such that the 1-planar graphs of diameter d have treewidth at most f(d); the same property holds more generally for the graphs that can be embedded onto a surface of bounded genus with a bounded number of crossings per edge.
They also have separators, small sets of vertices the removal of which decomposes the graph into connected components whose size is a constant fraction of the size of the whole graph.
For instance, this method leads to a polynomial-time approximation scheme for the maximum independent set of a 1-planar graph.
These graphs can always be drawn (in an outer-1-planar way) with straight edges and right angle crossings.
[21] By using dynamic programming on the SPQR tree of a given graph, it is possible to test whether it is outer-1-planar in linear time.
Ringel defined the local crossing number of G to be the least non-negative integer k such that G has a k-planar drawing.
[25] The k-planar graphs with n vertices have at most O(k1/2n) edges,[26] and treewidth O((kn)1/2).