ABSTRACT

Two-dimensional graph drawing, that is, graph drawing in the plane, has been widely studied. While this is not yet the case for graph drawing in 3D, there is nevertheless a growing body of research on this topic, motivated in part by advances in hardware for three-dimensional graphics, by experimental evidence suggesting that displaying a graph in three dimensions has some advantages over 2D displays [WF94, WF96, WM08], and by applications in information visualization [WF94, WM08], VLSI circuit design [LR86], and software engineering [WHF93]. Furthermore, emerging technologies for the nano through micro scale may create demand for 3D layouts whose design criteria depend on, and vary with, these new technologies. Not surprisingly, the mathematical literature is a source of results that can be regarded

as early contributions to graph drawing. For example, a theorem of Steinitz states that a graph G is a skeleton of a convex polyhedron if and only if G is a simple 3-connected planar graph. It is natural to generalize from drawing graphs in the plane to drawing graphs on other

surfaces, such as the torus. Indeed, surface embeddings are the object of a vast amount of research in topological graph theory, with entire books devoted to the topic. We refer the interested reader to the book by Mohar and Thomassen [MT01] as an example. Numerous drawing styles or conventions for 3D drawings have been studied. These styles

differ from one another in the way they represent vertices and edges. We focus on the most common ones and on the algorithms with provable bounds on layout properties and running time. In this chapter, by a drawing we always mean a graph representation (realization, layout,

embedding) where no two vertices overlap and no vertex-edge intersections occur unless there is a corresponding vertex-edge incidence in the combinatorial graph. We say that two edges cross if they intersect at a point that is not the location of a shared endpoint of the edges in the combinatorial graph. A drawing is crossing-free if no two edges cross.