Name
Abstract | ||
|---|---|---|
Directed graphs are commonly drawn by the Sugiyama algorithm, where crossing reduction is a crucial phase. It is done by repeated one-sided 2-level crossing minimizations, which are still ${\mathcal{NP}}$-hard. We introduce a global crossing reduction, which at any particular time captures all crossings, especially for long edges. Our approach is based on the sifting technique and improves the level-by-level heuristics in the hierarchic framework by a further reduction of the number of crossings by 5 – 10%. In addition it avoids type 2 conflicts which help to straighten the edges, and has a running time which is quadratic in the size of the input graph independently of dummy vertices. Finally, the approach can directly be extended to cyclic, radial, and clustered level graphs where it achieves similar improvements over the previous algorithms. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1007/978-3-642-11440-3_7 | WALCOM |
Keywords | Field | DocType |
crucial phase,level graph,long edge,sugiyama algorithm,particular time,reduction algorithm,level-by-level heuristics,global k-level,dummy vertex,previous algorithm,input graph,hierarchic framework,directed graph | Graph,Discrete mathematics,Combinatorics,Path (graph theory),Level crossing,Vertex (geometry),Algorithm,Quadratic equation,Binary decision diagram,Directed graph,Heuristics,Mathematics | Conference |
Volume | ISSN | ISBN |
5942 | 0302-9743 | 3-642-11439-3 |
Citations | PageRank | References |
6 | 0.44 | 11 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| christian bachmaier | 1 | 120 | 14.99 |
| Franz J. Brandenburg | 2 | 228 | 20.00 |
| Wolfgang Brunner | 3 | 44 | 4.96 |
| Ferdinand Hübner | 4 | 9 | 0.83 |