Planarization of Graphs Embedded on Surfaces

Abstract

A planarizing set of a graph is a set of edges or vertices whose removal leaves a planar graph. It is shown that if G is an n vertex graph of maximum degree d and orientable genus g, then there exists a planarizing set of O(sqrt(dgn)) edges. This result is tight within a constant factor. Similar results are obtained for planarizing vertex sets and for graphs embedded on nonorientable surfaces. Planarizing edge and vertex sets can be found in O(n+g) time if an embedding of G on a surface of genus g is given. We also construct an approximation algorithm that finds an O(sqrt(gn log g)) planarizing vertex set of G in O(n log g) time if no genus g embedding is given as an input.