Graph Planarization

Mauricio G.C. Resende and Celso C. Ribeiro

In Encyclopedia of Optimization, C. Floudas and P.M. Pardalos, eds., Kluwer Academic Publishers, vol. 2, pp. 368-373, 2001


This article is a survey of graph planarization.  Variants and applications of graph planarization are considered.  An exact branch and cut algorithm is described.  Heuristics based on a two-phase approach are then considered. Computational experiments comparing the various methods are reported.

PostScript file of full paper

Go back
Mauricio G.C. Resende's Home Page
Last modified: 28 June 2002

Copyright Notice