An effective crossing minimisation heuristic based on star insertion
share
We present a new heuristic method for minimising crossings in a graph. The method is based upon repeatedly solving the so-called star insertion problem and has several desirable characteristics for practical use. We introduce the method, discuss some aspects of algorithm design for our implementation, and provide some experimental results. The results indicate that our method compares well to existing methods, particularly for dense graphs, and is able to obtain some of the best known heuristic solutions to well-known instances.
READ FULL TEXT