Visualization of Structural Information: Automatic Drawing of Compound Digraphs

Summary of the Document:

Visualization of Structural Information: Automatic Drawing of Compound Digraphs

(Paper by Kozo Sugiyama and Kazuo Misue)

They suggested an effective algorithm that draws compound digraphs automatically. Both inclusion and adjacency edges are considered in the method.

Class of  Graphs p2

 Inclusion Digraph: D = (V, E) where E is a finite set of inclusion edges whose element (u, v) ∈ E means that u includes v.

Adjacent Digraph: D = (V, F) where F is a finite set of adjacency edges whose element (u, v) ∈  F means that u is adjacent to v. 

Readability Elements p2

1. Drawing Conventions: Fundamental constraints(necessary)
• Rectangle: A vertex is drawn as a rectangle
• Inclusive: If the graph is inclusion, that should be shown geometrically in the digraph, if not edges should be disjoint.
• Hierarchical: Vertices should be placed according to their relations(inclusion and adjacency)
• Down arrow: An adjacency edge (u,v) is drawn as downward arrow
2. Drawing Rules: Objectives satisfied as much as possible.
• Closeness: Connected vertices placed as closely as possible
• Line- crossing: Reducing the number of crossing between adjacency edges as much as possible
• Line-rect-crossing: Reducing  the number of crossing between adjacency edges and rectangles as much as possible
• Line straightness: Close adjacency edges are drawn as straight lines and far ones are drawn as polygonal lines while reducing number of bends and increasing the length of vertical part of the lines as much as possible
• Balancing: Placing  edges terminating and originating from a vertex in a balanced form

 Steps of the Algorithm p3

 Algorithm consists of 4 steps:

1. Hierarchization: First, checking for possibility of hierarchy when compound digraph is given. If there is no possibility, they determine reversed adjacency edges to assign compound level to each vertex and obtain an assigned compound diagram. But finding minimum edge set is NP-complete. So they used heuristic methods instead.
2. Normalization: An assigned compound digraph is converted to a proper compound digraph
3. Vertex ordering: In each local hierarchy, horizontal orders of vertices are determined to obtain Closeness, Line-crossing, and Line-rect-crossing rules as much as possible. Minimizing line-crossing and minimizing line-rect-crossing are NP-complete. Therefore they introduce heuristics for this problem.
4. Metrical layout: Horizontal positions of vertices are defined by applying Closeness, Line-straightness and Balancing rules as much as possible.