AN EFFICIENT GRAPH PLANARIZATION 2-PHASE HEURISTIC

Given a graph G = (V, E), the graph planarization problem is to find a largest subset F of E, such that H = (V, F) is planar. It is known to be NP-complete. This problem is of interest in automatic graph drawin g, in facilities layout, and in the design of printed circuit boards a nd integrated circuits. We present a two-phase heuristic for solving t he planarization problem. The first phase devises a clever ordering of the vertices of the graph on a single line and the second phase tries to find the maximal number of nonintersecting edges that can be drawn above or below this line. Extensive empirical results show that this heuristic outperforms its competitors. (C) 1994 John Wiley & Sons, Inc .