Search code examples
javascriptsvgd3.jsgraphcytoscape.js

Detect Graph Edges Overlapping

The problem: Looking for quite some time for a js graph library to create a directed graph (e.g. using dagre layout), with the constrain of non-overlapping edges.

Steps until now

  1. Started with cytoscape.js but as it seems, such a feature doesn't exist.
  2. Continued on with an svg based solution (considering that all elements are in the DOM), d3.js using the dagre-d3, but still the information in the DOM is the path route.

Objective

  1. Find a way to detect edge overlapping, either canvas or svg based.
  2. Create a custom layout to respect this constrain. Will use this as a metric for my convergence algorithm.

Graphical Representation

Below a graphical representation of the objective. I want to detect that edges 0>1 and 2>3 are overlapping.

Any ideas, thoughts are welcome. If there is something wrong with my logic, corrections/suggestions are more than welcome. enter image description here

Solution

  • Finding edge crossings (line intersections) is a fairly simple bit of geometry which is explained here --> https://stackoverflow.com/a/18234609/368214

    But then minimising such edge crossings in a graph (zero edge crossings are only possible in planar graphs) is one of the great research challenges of graph layout - https://cs.stackexchange.com/questions/14901/how-to-reduce-the-number-of-crossing-edges-in-a-diagram

    Some graph layouts for specific graph types like DAGS such as Sugiyama aim to reduce crossings and similar cytoscape layouts are available at yfiles if that helps (i.e. the hierarchic layout) --> http://apps.cytoscape.org/apps/yfileslayoutalgorithms