Planar Induced Subgraphs of Sparse Graphs - Graph Drawing - page 1

Planar Induced Subgraphs of Sparse Graphs
Glencora Borradaile 1 , David Eppstein 2 , and Pingan Zhu 1
1 Oregon State University, Corvallis OR 97330, USA
2 University of California, Irvine, Irvine CA 92697, USA
Abstract. We show that every graph has an induced pseudoforest of
at least n − m/ 4 . 5 vertices, an induced partial 2-tree of at least n −
m/ 5 vertices, and an induced planar subgraph of at least n − m/ 5 . 2174
vertices. These results are constructive, implying linear-time algorithms
to find the respective induced subgraphs. We also show that the size of
the largest K h -minor-free graph in a given graph can sometimes be at
most n − m/ 6+ o ( m ).
1 Introduction
Planarization , a standard step in drawing non-planar graphs, involves replacing
edge crossings with new vertices to form a planar graph with paths that represent
the original graph's edges. Incremental planarization , does this by finding a large
planar subgraph of the given graph, and then adding the remaining features of
the input graph one at a time [6]. Thus, it is of interest to study the algorithmic
problem of finding planar subgraphs that are as large as possible in a given
graph. Unfortunately, this problem is NP-hard and, more strongly, MAX-SNP-
hard [4]. A trivial algorithm, finding an arbitrary spanning tree, achieves an
approximation ratio of 3 , and by instead searching for a partial 2-tree this ratio
can be improved to 5 [4]. The equivalent complementary problem, deleting a
minimum number of edges to make the remaining subgraph planar, is fixed-
parameter tractable and linear time for any fixed value of the parameter [12].
In this paper we study a standard variant of this problem: finding a large
planar induced subgraph of a given graph. In the context of the planarization
problem, one possible application of finding this type of planar subgraph would
be to apply incremental planarization in a drawing style where edges are rep-
resented as straight-line segments. A planar induced subgraph can always be
drawn without crossings in this style, by Fary's theorem, after which the partial
drawing could be used to guide the placement of the remaining vertices. As with
the previous problem, the induced planar subgraph problem is NP-hard, but
again there is a linear-time fixed-parameter tractable algorithm for the equiv-
alent problem of finding the smallest number of vertices to delete so that the
remaining induced subgraph is planar [11].
Because of the diculty of finding an exact solution to this problem, we
instead seek worst-case guarantees: what is the largest size of a planar induced
subgraph that we can be guaranteed to find within a graph of a given size? In
this we are inspired by a paper of Alon, Mubayi, and Thomas [1], who showed