Drawing Layered Hypergraphs
Orthogonally drawn hypergraphs have important applications, e.g. in actor-oriented data flow diagrams for modeling complex software systems. Graph drawing algorithms based on the approach by Sugiyama et al. place nodes into consecutive layers and try to minimize the number of edge crossings by finding suitable orderings of the nodes in each layer. With orthogonal hyperedges, however, the exact number of crossings is not determined until the edges are actually routed in a later phase of the algorithm, which makes it hard to evaluate the quality of a given node ordering beforehand. In this report, we present and evaluate two crossing counting algorithms that predict the number of crossings between orthogonally routed hyperedges much more accurately than previous methods. We also describe methods for routing hyperedges that span multiple layers and for handling junction points.