Virtual Nodes

Once the levels have been assigned, there still exists the problem of edges crossing nodes because two nodes can be separated by more than one level. An example of this is shown in Figure 1. The edge between node c and node f crosses level 2.

To avoid this problem, we introduce virtual nodes into our graph. Virtual nodes are created on every level in between the separated nodes. Edges are then drawn connecting each virtual node and the virtual nodes on either end to the original nodes. This guarantees that edges will no longer cross nodes on intermediate levels. Figure 2 shows Figure 1 after virtual nodes have been inserted. The virtual node on level 2 prevents the edge from crossing through node e on level 2.

At this point, we have had few problems with expressing virtual nodes in this manner. However, there is a potential for this virtual node system to become problematic in larger graphs. Currently, we a researching ways to better express virtual nodes (perhaps through splines).

Figure 1: An example of an edge that crosses more than one level

Figure 2: An example of an edge that crosses more than one level using virtual nodes

Figure 3: An DSDS window from the program wc

(Postscript version of diagram available.)

Copyright © 1994, 1995    Keith B. Gallagher, Bradley M. Kuhn, Dennis J. Smith.

Verbatim copying and distribution of this entire paper is permitted in any medium, provided this notice is preserved.