Improving readability of static, straight-line graph drawings: A first look at edge crossing resolution through iterative vertex splitting

We present a novel vertex-splitting approach with which to iteratively resolve edge crossings in order to improve the readability of graph drawings. Dense graphs, even when small in size (10 to 15 nodes in size) quickly become difficult to read with increasing numbers of edges, and form so-called “hairballs”. The readability of a graph drawing is measured using many different quantitative aesthetic metrics. One such metric of particular importance is the number of edge crossings. Classical approaches to improving readability, such as the minimization of the number of edge crossings, focus on providing overviews of the input graph by aggregating or sampling vertices and/or edges. However, this simplification of the graph drawing does not allow for detailed views into the data, as not all vertices or edges are rendered, and also requires sophisticated interaction approaches to perform well. To avoid this, our locally optimal vertex splitting approach aims to minimize the number of remaining edge crossings while also minimizing the number of vertices that need to be split. In each iteration, we identify the vertex contributing the largest number of edge crossings, remove it, locate the embedding locations of said vertex’s two split copies, and determine each copy’s unique adjacency. We conduct a user study with 52 participants to evaluate whether vertex splitting affects users’ abilities to conduct a set of graph analytical tasks on graphs 12 nodes in size. Users were tasked with identifying a vertex’s adjacency, determining the shared neighbors of two vertices, and checking the validity of a set of paths. We ultimately conclude that within the context of small, dense graphs, systematic vertex splitting is preferred by participants and even positively impacts user performance, though at the cost of the time taken per task.