Compaction of Orthogonal and Hierarchical Graph Drawings Using Constraint Graphs and Minimum Cost Flows

Automatic graph drawing has become a wide research field in the past decades. The central task is to compute a nice drawing of a graph that is easy to read and understand. There are different drawing styles that determine the general look of a graph drawing. Certain attributes of the drawing should be minimized or maximized for an aesthetic visualization. Two important criteria for every drawing style are the drawing area and the total edge length. A drawing should not be unnecessarily wide or high and the edges should be as short as possible. At the same time, readability should be maintained. The compaction of graph drawings deals with this issue. In this thesis, we consider the compaction problem within two specific drawing styles. In orthogonal drawings, the edges are drawn as a sequence of horizontal and vertical line segments. In hierarchical drawings, the vertices are placed on horizontal layers and the edges point downward. To solve the compaction problems, we model them as minimum cost flow problems and potential assignment problems in constraint graphs. We present methods to minimize the width or height of a drawing, the total horizontal or vertical edge length or a combination of both. For the orthogonal drawing style we introduce a compaction approach that further reduces the drawing area and total edge length by adding bends to the edges.