2
$\begingroup$

I have a hierarchical graph structure on a vertical timeline with nodes that have a fixed y coordinate. I am now looking for:

  1. an algorithm (suggestions, any related papers, anything at all) to optimize the x of each node to reduce edge crossings (and generally increase graph readability).
    • One idea that I have been exploring is a grid layout: my nodes already have specific rows (one per row) but determining the column for each node (or node group) is the difficult part.
  2. (not as important) an algorithm to draw edges while minimizing clutter. Most algorithms have straight edges, but I would not mind trying something else, where, for example, in a grid layout, I optimize edges by finding the cells the edges should go through. I know that straighter or just short edges are generally better, but maybe there is something that can be improved here as well?

So far, the algorithms I found are limited to unconstrained nodes and, except for some papers on edge bundling, do not discuss optimizing the edge path itself.

Any help/keywords/papers, anything really, would be largely appreciated!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

One plausible approach would be to adapt a graph drawing algorithm algorithm to your situation. Some of them use optimization (e.g., force-based layout algorithms); it should be easy to adapt them by treating the $y$-coordinate of each point as a fixed constant and only optimizing the values of the $x$-coordinates. I don't know whether this will minimize the number of edge crossings, but it seems plausible it might do a reasonable job.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.