Volume 11, Number 18, November 2021

Method for Orthogonal Edge Routing of Directed Layered Graphs with Edge Crossings Reduction

  Authors

Jordan Raykov, JDElite Consulting, USA

  Abstract

This paper presents a method for automated orthogonal edge routing of directed layered graphs using the described edge crossings reduction heuristic algorithm. The method assumes the nodes are pre-arranged on a rectangular grid composed of layers across the flow direction and lanes along the flow direction. Both layers and lanes are separated by rectangular areas defined as pipes. Each pipe has associated segment tracks. The edges are represented as orthogonal polylines consisting of line segments and routed along the shortest paths. Each segment is assigned to a pipe and to a segment track in it. The edge crossings reduction uses an iterative algorithm to resolve crossings between segments. Conflicting segments are reassigned to adjacent segment tracks, either by swapping with adjacent segments, or by inserting new tracks and calculating the shortest paths of edges. The algorithm proved to be efficient and was implemented in an interactive graph design tool.

  Keywords

Directed Graphs, Orthogonal Edge Routing, Crossings Reduction Algorithms.