  We present a thorough experimental evaluation of several crossing
minimization heuristics that are based on the construction and iterative
improvement of a planarization, i.e., a planar representation of a graph with
crossings replaced by dummy vertices. The evaluated heuristics include
variations and combinations of the well-known planarization method, the
recently implemented star reinsertion method, and a new approach proposed
herein: the mixed insertion method. Our experiments reveal the importance of
several implementation details such as the detection of non-simple crossings
(i.e., crossings between adjacent edges or multiple crossings between the same
two edges). The most notable finding, however, is that the insertion of stars
in a fixed embedding setting is not only significantly faster than the
insertion of edges in a variable embedding setting, but also leads to solutions
of higher quality.
