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