I've been working on a new Wikipedia article on linkless embedding of graphs into three-dimensional space. While doing so, I uncovered an interesting 3d graph drawing problem that was asked by Horst Sachs in 1981 and appears to still be unanswered.

Linkless graphs are the graphs that can be drawn in space so that no two cycles have nonzero linking number. A closely related concept is that of a "flat embedding", in which each cycle should be the boundary of a disk that is not crossed by any other feature of the graph; every linklessly embeddable graph has a flat embedding. I wrote about linkless graphs in my SoCG 2010 conference report: Ken-ichi Kawarabayashi spoke at SoCG about a linear time algorithm he had developed with Kreutzer and Mohar for recognizing them and finding embeddings of them.

Sachs' question concerns spatial analogues of Fáry's theorem, the result that any planar graph can be drawn in the plane with straight line segment edges. Linkless embeddings are defined topologically rather than geometrically: edges are allowed to be represented as curves or polygonal chains rather than as straight line segments. Does every linkless graph have a straight-line linkless embedding?

Sachs' writeup actually includes a stronger problem: does every linkless embedding of a graph have a homeomorphic straight-line embedding? But as he hints, the answer to this stronger question is no: for instance, a triangle graph can be embedded in space to form a trefoil knot with curved edges, and this embedding is linkless (there are no two disjoint cycles to be linked); however, according to calculations of the stick number of the trefoil the shortest cycle that has a homeomorphic straight-line embedding is the 6-cycle. So not every linkless embedding of the triangle can be straightened. But perhaps restricting attention to flat embeddings avoids this problem: in a flat embedding, none of the cycles can be knotted. So: does every flat embedding of a graph have a homeomorphic straight-line embedding?