1-planar graph

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).