## Dummy vertex additions for eliminating all crossings

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