A technique for drawing directed graphs

1993/03/01 by Emden R. Gansner, E.R. Gansner, E. Koutsofios +3 · 9 citations
Computer Science · #Algorithm #Artificial intelligence #Computational Geometry and Mesh Generation #Computer science #Data Management and Algorithms #Data Visualization and Analytics #Graph #Heuristic #Theoretical computer science #Vertex (graph theory)

paper · doi:10.1109/32.221135

openalex publication_date 1993/03/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04

Abstract

A four-pass algorithm for drawing directed graphs is presented. The fist pass finds an optimal rank assignment using a network simplex algorithm. The seconds pass sets the vertex order within ranks by an iterative heuristic, incorporating a novel weight function and local transpositions to reduce crossings. The third pass finds optimal coordinates for nodes by constructing and ranking an auxiliary graph. The fourth pass makes splines to draw edges. The algorithm creates good drawings and is fast.>

Cited by

• HySE: A Force‐Directed Layout Algorithm for Directed and Mixed Graphs
• VEIL: Reading Control Flow Graphs Like Code
• CPSLint: A Domain-Specific Language Providing Data Validation and Sanitisation for Industrial Cyber-Physical Systems
• Structural Tree Extraction from 3D Surfaces
• GASP: A Gradient-Aware Shortest Path Algorithm for Boundary-Confined Visualization of 2-Manifold Reeb Graphs
• Visual Execution and Validation of Finite-State Machines and Pushdown Automata
• Design Support for Multitape Turing Machines
• Developing and evaluating quilts for the depiction of large layered graphs
• DREAMS: Modelling Support for Research into Engineering and Artistic Design