ATTENTION: An updated version of this page is now available HERE , which includes all edges of K100 in the java applet, and also a link to VRML versions of the construction.

A 3-d representation of K100- the complete graph on 100 vertices.
Each mouse click displays a different Z-plane with edges shown in blue.
The planes are organized into groups - boxes that are dx, dy apart are
joined in batches defined by the variable offset.
Only values of dx and dy >0 are displayed here.
See * Orthogonal 3-D Graph Drawing * by
T. Biedl, T. Shermer, S. Whitesides and S. Wismath for details.

In the same paper, we have shown a lower bound for the problem in general. The following pictures (generated with POVRay) illustrate 3 cases in the proof:

A construction of volume O(n^2.5), which thus matches the proven lower bound, is also described. The following figure shows the basic shape of the drawing. The Java applet above displays a sequence of Z planes required to embed the edges crossing free.