most recent 30 from http://mathoverflow.net 2013-05-22T07:42:56Z http://mathoverflow.net/feeds/question/56282 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/56282/dummy-vertex-additions-for-eliminating-all-crossings Nikolaos Kavvadias 2011-02-22T13:40:46Z 2011-02-22T13:40:46Z

<p>Hi all,</p> <p>does anyone know any algorithm for adding vertices to a digraph (in general) or DAG (as a special case) to eliminate all crossings? </p> <p>Of interest are two variants of the problem:</p> <p>a) use the minimum number of added vertices</p> <p>b) force an almost-upward planarization of the original graph ("almost" means that certain types of backedges are acceptable).</p> <p>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).</p> <p>Thanks</p> <p>Nikolaos Kavvadias</p>