Introduction
Visualizing large or dense graphs often results in "hairballs"—drawings cluttered with edge crossings that obscure the underlying structure and hinder readability. While dynamic visualizations can alleviate this by showing the graph over time, they introduce a significant challenge: maintaining the user's "mental map." If vertex positions change between frames, the viewer loses track of the data's context.
This paper introduces the concept of planar stories, a novel framework designed to visualize complex graphs by decomposing them into a sequence of crossing-free (planar) frames. By keeping vertex positions fixed throughout the sequence, the framework ensures stability while maximizing clarity through the elimination of edge crossings.
The Problem: Balancing Stability and Complexity
A "planar story" is defined as a sequence of frames where each frame is a planar subgraph of the original drawing. To transition between frames, the authors propose a model where one new edge enters in each step. If this new edge crosses any existing edges, those crossing edges are removed to maintain planarity.
The primary optimization goal is to find a min-frame optimal story. This means maximizing the minimum number of edges shown in any single frame of the sequence. This prevents "sparse" frames that provide little information, ensuring that the visualization remains informative throughout the entire transition.
Algorithmic Framework
The authors tackle the problem using two distinct approaches:
1. Integer Linear Programming (ILP)
The authors provide an exact ILP formulation to find the absolute optimal planar story. While this model guarantees the best possible result, it is computationally intensive. For dense real-world graphs, the ILP often fails to reach a solution within a reasonable timeframe (e.g., 15 minutes), necessitating more efficient alternatives.
2. Advanced Greedy Heuristics
To handle larger datasets, a two-phase heuristic framework was developed:
- Phase 1 (Initialization): The algorithm identifies two large, edge-disjoint planar subgraphs to serve as the anchor points (the start and end) of the story.
- Phase 2 (Iterative Selection): The algorithm iteratively selects "admissible" edges to add to the current frame. Selection is based on "current degree"—the number of active edges a candidate edge would cross.
The study highlights a "Pareto optimal" approach (Variant 1a) that balances the size of the initial edge set against the final set, proving highly effective in practice.
Experimental Evaluation
The researchers evaluated their algorithms on a benchmark of 637 graph instances, including:
- Geometric Graphs: 200 random Erdős–Rényi graphs and 12 real-world networks (social and road maps) using force-directed layouts.
- Crossing Graphs: 425 instances where the "crossing graph" (where nodes represent edges and links represent crossings) possessed specific structural properties like trees or planar structures.
Key Results and Insights
- Heuristic Effectiveness: The best greedy variants (AG-1a2a and AG-1a2b) achieved an average approximation ratio of approximately 95% compared to the optimal ILP solutions.
- Efficiency vs. Quality: While the ILP is superior in quality, the "Variant 1c" heuristic emerged as a practical "sweet spot," running in milliseconds while maintaining an 80–88% approximation ratio.
- The "Non-Maximal" Paradox: A significant finding was that starting a story with a maximal planar subgraph (one where no more edges can be added without a crossing) is often sub-optimal. Smaller initial sets can sometimes lead to smoother transitions and higher edge counts in subsequent frames.
- Crossing Graph Centrality: The difficulty of the problem is tied more to the structure of the crossing graph than the size of the original graph itself. If the crossing graph is simple (like a tree), the problem becomes much easier to solve.
Conclusion and Future Directions
The planar story framework provides a robust method for untangling dense graph drawings without sacrificing the user's mental map. While the authors successfully solved the 2-plane case (where edges cross at most twice), the complexity of 3-plane graphs remains an open theoretical question.
Future work aims to address "story length" by exploring compression techniques—adding multiple non-crossing edges simultaneously. Additionally, the authors suggest investigating how different initial graph layout algorithms impact the quality of the resulting planar stories.
Summary updated