How to Draw Graphs: Seeing and Redrafting Large Networks in Security and Biology
This addresses visualization challenges for researchers and practitioners in fields like security and biology who work with large networks, though it appears incremental as it builds on existing graph drawing techniques.
The paper tackled the problem of undesirable properties in graph drawing methods, such as edge intersections, unclear edge labeling, and visual density in large networks, by introducing a new cartographic method that solves these issues and offers additional advantages like better representation of graph complements and comparisons.
A graph is a mathematical object consisting of a set of vertices and a set of edges connecting vertices. Graphs can be drawn on paper in various ways, but until recently all published methods of drawing graphs have had undesirable properties: (i) for graphs which are not plane embeddable, intersections between the lines representing edges appear at points which are not vertices, creating the appearance of vertices where none exist, (ii) vertex labels can be placed inside vertex symbols, but there is no consistent, logical, and visually clean place to put edge labels, and (iii) representations of large graphs are visually dense and difficult to interpret. This paper describes a new cartographic method of drawing graphs which solves all of these problems, and has other advantages as well. Complements, comparisons and contrasts of graphs are usually better shown cartographically than in node-link form.