Eliminating intersections in drawings of graphs

Graphs (or networks), are ubiquitous mathematical structures representing pairwise interactions (edges) between objects (the nodes or vertices of the graph). The study of large graphs is becoming more and more crucial in biology, bioinformatics, finance, sociology, and many other scientific disciplines. In applications, graphs are often specified purely abstractly, through a list of vertices and edges, and in order to facilitate reasoning about them, it is important to visualize them. One of the most common mathematical models for visualizing graphs are graph drawings, in which the vertices are represented by points and edges by curves between their endpoints. The ever- increasing demand for software visualizing large graphs is a major driving force behind the research on algorithms for producing graph drawings automatically; another major impetus for this area of research, which has been very active since the 1980s, is provided by applications such as integrated circuits design. Depending on a particular application, a desired drawing of the graph must satisfy particular quality measures. A particularly important parameter is the number of crossings between edges, whose minimization is one of the key mathematical challenges in automated visualization of graphs. The purpose of the proposed project is two-fold. On the one hand, we aim to develop mathematical tools helpful in the design of fast graph drawing algorithms that minimize the number of edge crossings, under additional constraints. Our approach is based crucially on the Hanani-Tutte paradigm which reduces the detection of the existence of the desired crossing-free drawing of a graph to the algebraic problem of solving a system of linear equations. For this problem provably fast algorithms exist. On the other hand, along the way we intend to address several fundamental open problems about higher dimensional analogs of graphs, and graphs drawn in the plane and on more complicated surfaces, whose resolution would likely have a large impact on the area of graph/network visualization, as well as on the area of combinatorial and computational geometry. Some fundamental and easily explainable questions that we are interested in are the following: What is the minimum number of crossings in a drawing of the graph in the plane? Is this number always the same as the minimum number of pairs of crossing edges? Surprisingly, it has been an open problem for decades to determine if there exists a graph for which these numbers differ. A thrackle is a planar drawing of a graph in which each pair of edges meet exactly once, either at a common endpoint or in a proper crossing. It has been open for almost half a century to decide if a thrackle can have more edges than vertices.

Devising automated human readable graph-based visualizations entails a lot of challenges. The challenges are due to conflicting quality measures that a desired visualization must satisfy, for example, the readability versus the entirety of the representation, or the size of features versus the total size. We concentrate on the trade-off between the readability and the entirety of the representation. Large networks arising in applications with millions of nodes and connections between them are unreadable if visualized in their entirety, and without compromising the totality we end up with an unreadable clutter. A common solution to this problem is to endow the graph with a hierarchy of clusters and at each time visualize only locally related clusters. To improve the readability of graph visualizations even further we wish to minimize the number of crossings between the curves, which is one of the key computational challenges in automated visualization of graphs. Motivated by theses considerations, we studied graph-based structures, so-called obstructions, that enforce crossings in any representation on surfaces such as plane, torus, double torus, etc. As one of our main achievements, we proved that a certain elegant approach for identifying obstructions does not work on complicated surfaces. This was an attractive open problem in the theory of topological graphs. Another main outcome of our work is the first fast algorithm for so-called clustered planarity. The existence of a fast algorithm for clustered planarity was a well-known longstanding open problem in theoretical computer science central to the area of graph drawing. Our algorithm determines if a graph equipped with a hierarchical clustering can be visualized without crossings while respecting the given clustering in a certain natural sense. We think that the algorithm and its variants would be suitable to serve as a basic building block of an automated graph visualization system.