Orthogonal graph drawing with constraints
Markus Eiglsperger, Ulrich Fößmeier, Michael Kaufmann · 2000
One of the primary prerequisites of drawing a graph directly from practical application is that the user must be able to formulate constraints for the layout. We introduce a concept to incorporate various kinds of constraints in the welt-known model for bendminimizing orthogonal drawings for planar and nonplanar graphs which was originally based on a min-cost-flow approach. Using ILP formulations, we drastically improve the flexibility of the basic system and enable a possibly effective user interaction while ensuring efficient algorithms. Via some examples we are able to demonstrate our realization of this concept. 1 In t roduct ion There are two main purposes of graph visualization: The first one is to show small or medium sized graphs in an exquisite way as it can be done manually. The second goal is to visualize structural properties of large graphs. Methods of automatic drawing mainly try to meet the second demand, they follow certain criteria, such as minimizing the area, the number of crossings, and so on. Only a small number of methods have been developed to support user interaction and to keep the algorithms flexible enough to incorporate user requirements for parts of the drawing. Examples of such constraints are • the directions of the edges are prescribed (upward, rightward) • the places are fixed, where certain edges are at-tached to the vertices (port constraints) • some segments of the edges have a certain length (to enable labeling!). Attempts to include constraints in graph drawing algo-rithms have been mostly directed to global requirements such as 'no crossings are allowed ' (for planar graphs), 'upward drawings ' (Sugiyama style), etc. (see [6] for an overview.) All these approaches lack the flexibility to