# Graph Layout Algorithm that optimizes only x (not y) of nodes?

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!

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.