Liebers, Annegret

Planarizing graphs---a survey and annotated bibliography

J. Graph Algorithms Appl. 5(1), 74 p. (2001)


Summary: Given a finite, undirected, simple graph G, we are concerned with operations on G that transform it into a planar graph. We give a survey of results about such operations and related graph parameters. While there are many algorithmic results about planarization through edge deletion, the results about vertex splitting, thickness, and crossing number are mostly of a structural nature. We also include a brief section on vertex deletion. We do not consider parallel algorithms, nor do we deal with on-line algorithms. Communicated by A. Gibbons: submitted June 1996; revised December 1998 and January 2001. Research supported in part by DFG grant Wa 654/10-2.