Extending Fary's Theorem to non-planar graphs: 1-planar graphs


My latest work has generalised Fary's well-known theorem (1948) on straight-line representations of "planar" graphs to certain classes of non-planar graphs. One of the most common graph drawing conventions is the straight-line drawing convention, that edges are straight-line segments. Existing straight-line drawing algorithms have a strong assumption that the input graph is planar. In practice, however, most graphs arising from real-world applications are non-planar.
My innovation was to relax the assumption of planarity, to sparse non-planar graph classes such as "k-planar graphs" (i.e., each edge has at most k crossings) and "k-skewness graphs" (i.e. graphs whose removal of k edges result in planar graphs). These optimal algorithms can construct straightline drawings of such non-planar graphs in linear time.


P. Eades, S. Hong, G. Liotta, S. Poon, "Fary's Theorem for 1-planar Graphs", TR IT-IVG-2012-01, School of IT, University of Sydney, 2012.

Fary's theorem states that every plane graph can be drawn as a straightline drawing. A plane graph is a graph embedded in a plane without edge crossings. In this paper, we extend Fary's theorem to non-planar graphs. More specifically, we study the problem of drawing 1-plane graphs with straight-line edges. A 1-plane graph is a graph embedded in a plane with at most one crossing per edge.We give a characterisation of those 1-plane graphs that admit a straight-line drawing. The proof of the characterisation consists of a linear time testing algorithm and a drawing algorithm. We also show that there are 1-plane graphs for which every straight-line drawing has exponential area. To our best knowledge, this is the first result to extend Fary's theorem to non-planar graphs.