An effective crossing minimisation heuristic based on star insertion

Kieran Clancy, Michael Haythorpe, Alex Newcombe

We present a new heuristic method for minimising crossings in a graph. The method is based upon repeatedly solving the so-called {\em star insertion problem} in the setting where t…