Hi all,
does anyone know any algorithm for adding vertices to a digraph (in general) or DAG (as a special case) to eliminate all crossings?
Of interest are two variants of the problem:
a) use the minimum number of added vertices
b) force an almost-upward planarization of the original graph ("almost" means that certain types of backedges are acceptable).
I just call those vertices "dummy" since they should alter the meaning conveyed by a semantic graph (e.g. a computational graph for representing a program).
Thanks
Nikolaos Kavvadias
