Premium
An efficient graph planarization two‐phase heuristic
Author(s) -
Goldschmidt Olivier,
Takvorian Alexan
Publication year - 1994
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230240203
Subject(s) - chemical mechanical planarization , heuristic , graph , computer science , planar graph , line graph , electronic circuit , planar , mathematical optimization , mathematics , algorithm , combinatorics , theoretical computer science , engineering , polishing , electrical engineering , mechanical engineering , computer graphics (images)
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 drawing, in facilities layout, and in the design of printed circuit boards and integrated circuits. We present a two‐phase heuristic for solving the 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. © 1994 by John Wiley & Sons, Inc.