Crossing minimisation Heuristics for 2-page drawings
journal contributionposted on 25.09.2006 by Hongmei He, Ondrej Sykora, Imrich Vrt'o
Any type of content formally published in an academic journal, usually following a peer-review process.
The minimisation of edge crossings in a book drawing of a graph G is one of important goals for a linear VLSI design, and the two-page crossing number of a graph G provides an upper bound for the standard planar crossing number. We propose several new heuristics for the 2-page drawing problem and test them on benchmark test sets like Rome graphs, Random Connected Graphs and some typical graphs. We get exact results of some structural graphs, and compare some of the experimental results with the one in paper.
- Computer Science