A GRASP for graph planarization

Journal Article


A greedy randomized adaptive search procedure (GRASP) is a metaheuristic for combinatorial optimization. In this paper, we describe a GRASP for the graph planarization problem, extending the heuristic of Goldschmidt and Takvorian [Networks 24 (1994) 69–73]. We review the basic concepts of GRASP: construction and local search algorithms. The implementation of GRASP for graph planarization is described in detail. Computational experience on a large set of standard test problems is presented. On almost all test problems considered, the new heuristic either matches or finds a better solution than previously described graph planarization heuristics. In several cases, previously unknown optima solutions are found. © 1997 John Wiley & Sons, Inc. Networks 29: 173–189, 1997

Related Topics

Related Publications

Related Content

Site Footer


This website is provided by John Wiley & Sons Limited, The Atrium, Southern Gate, Chichester, West Sussex PO19 8SQ (Company No: 00641132, VAT No: 376766987)

Published features on are checked for statistical accuracy by a panel from the European Network for Business and Industrial Statistics (ENBIS)   to whom Wiley and express their gratitude. This panel are: Ron Kenett, David Steinberg, Shirley Coleman, Irena Ograjenšek, Fabrizio Ruggeri, Rainer Göb, Philippe Castagliola, Xavier Tort-Martorell, Bart De Ketelaere, Antonio Pievatolo, Martina Vandebroek, Lance Mitchell, Gilbert Saporta, Helmut Waldl and Stelios Psarakis.