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
K2,2,2,2,
K3,3,3
and K6,6.
You will need a VRML browser
to view these drawings. These drawings are of interest because of the following
unsolved problem:
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? Eades, Symvonis and Whitesides (GD'96), who first mentioned this problem, conjecture that the answer is false. |
|
People doing orthogonal graph drawing |
Publications on orthogonal graph drawing
Systems for 2D orthogonal graph drawing
Systems for 3D orthogonal graph drawing |