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.