Orthogonal Graph Drawing
an orthogonal graph drawing each edge is represented by an axis-parallel
polyline. Such drawings have applications in VLSI circuit layout
and information visualization. The automatic production of three-dimensional
orthogonal graph drawings was the topic of my Ph.D.
thesis. I became interested in this topic having discovered the
2-bend 3-D orthogonal drawing of K7
(shown to the right), which was previously conjectured not to exist. (This
viewpoint is due to Richard
Webber.) Compare this 2-bend drawing with this 4-bend drawing of K7.
Some other 2-bend 3-D orthogonal drawings that I have discovered include
You will need a VRML browser
to view these drawings. These drawings are of interest because of the following
2-Bends Problem: Does every simple graph with maximum degree
6 have a 3-D orthogonal graph drawing with at most 2 bends per edge?
and Whitesides (GD'96), who first mentioned this problem,
conjecture that the answer is false.