A Divide-and-Conquer Algorithm for the Automatic Layout of Large Directed Graphs

Abstract

Pictures are a useful medium for communicating abstract information. Pictures exploit a person’s natural abilities to recognize and understand visual patterns. However, the differences between an effective and a confusing presentation of the same data can be subtle, and often depend on the layout. Methods for automatic presentation of relational information in the form of directed graphs are discussed. An overview of the graph-layout problem is presented, along with a summary of several different layout algorithms. A new divide-and-conquer layout algorithm is described in detail. This algorithm produces especially good results on large graphs of several hundred vertices. © 1991 IEEE