Orthogonal Graph Drawing

In 2-bend K_7 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 K (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

  • The recent survey by Markus Eiglsperger, Sándor Fekete and Gunnar W. Klau. (© Springer)
  • The publications of the above people.

Systems for 2D orthogonal graph drawing

Systems for 3D orthogonal graph drawing


Back to home ...
web counter