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.