Avoiding crossings in non-planar graph layouts

Abstract

Reducing crossings in node-link diagrams of networks is a topic of great interest in graph drawing and information visualization. When viewed from the perspective of graph drawing this problem is often studied via considering the underlying graph without using any further semantic information present in the network. A drawing of this graph in the Euclidean plane is then commonly defined by mapping vertices to points and edges to simple curves between the vertices they connect. Finding a layout with as few crossings as possible can then be formulated as finding such a drawing with the minimum number of intersections between the curves that represent the edges. As this proves to be a computationally very difficult problem, researchers have turned to other methods to reduce the visible crossings in drawings of non-planar graphs. In this thesis we study methods that modify and manipulate the way we draw the edges in a drawing of a graph, while keeping the principle idea of node-link diagrams intact. To facilitate thinking about the ways edges can be modified we first identify three coarse categories of possible modifications when an initial drawing is given and the vertices are not to be moved. The three principle ideas we identify are to re-route the edges, changing where they are drawn but not how, drawing the edges using a different metaphor, meaning we do not change where the edge is drawn but how, and approaches that allow both, re-routing and changing the style of drawing we use to represent the edges. Each principal method is investigated through the lens of a specific type of layout. We re-route edges in circular and mixed linear layouts, we make all crossings disappear by deleting as little parts as possible of the edges in partial edge drawings, and we bundle edges in our exploration of strict confluent drawings to create seemingly plane layouts of highly non-planar graphs. As most of these modification problems prove to be NP-hard we desire to identify good restrictions and special cases to make the problems tractable. One possibility is to restrict the graph classes we are interested in. Hence reducing the complexity of the possible graphs that have to be considered. Another way is to analyse what makes the problem difficult in the fist place. Here, we fix a parameter and study if the problem can be solved in polynomial time in the input size when we allow arbitrary computation time in the parameter. For the first possibility we will mostly be interested in classes defined by the intersections of geometric objects in the plane. For the second possibility we employ the rich toolkit of fixed-parameter tractability to refine the complexity of problems and to identify suitable exact algorithms using natural and structural parameters or show that under standard complexity theoretic assumptions no such algorithms can exist. Where possible we also implemented our algorithms and demonstrate their usefulness for small and mid size instances.