Evaluating and Extending Speedup Techniques for Optimal Crossing Minimization in Layered Graph Drawings

Area of Science:

• Graph theory and visualization
• Computer science
• Operations research

Background:

• Layered graphs are crucial for visualizing temporal and hierarchical data.
• Minimizing edge crossings is key to improving layered graph readability.
• Existing heuristic methods lack optimality; optimal methods face scalability challenges.

Purpose of the Study:

• To categorize and evaluate state-of-the-art linear programming (LP) formulations for exact crossing minimization in layered graphs.
• To identify and assess techniques for accelerating LP-based optimal layered graph layout algorithms.
• To improve the scalability and applicability of optimal methods for larger graphs.

Main Methods:

• Categorization and evaluation of existing LP formulations for crossing minimization.
• Description and implementation of nine new and existing acceleration techniques.
• Computational evaluation of technique performance, interaction, and impact on calculation time.

Main Results:

• Identified and evaluated multiple techniques to accelerate exact crossing minimization algorithms.
• Demonstrated that the best-performing techniques yield median improvements of 2.5-17x, depending on the solver.
• Showcased the ability to generate optimal layered graph layouts faster and for larger datasets.

Conclusions:

• The proposed techniques significantly enhance the computational performance of optimal layered graph layout algorithms.
• Researchers and practitioners can adapt these techniques to optimize layouts based on specific graph characteristics.
• An open-source Python implementation is provided, facilitating the adoption of improved optimal layout generation.