Information Technology Reference
In-Depth Information
that every triangle-free input graph with n vertices and m edges contains an
induced forest with at least n
m/ 4 vertices. This is tight, as shown by an input
graph in the form of n/ 4 disjoint copies of a 4-cycle. Induced forests are a special
case of induced planar subgraphs, and so this result guarantees the existence of
an induced planar subgraph of n
m/ 4 vertices. As we show, an analogous
improvement to the one in the approximation ratio for planar subgraphs can
be obtained by seeking instead an induced partial 2-tree. Rossmanith [3] has
posed the question: does every graph have an induced planar subgraph of size
n
m/ 6? We shrink the gap on the worst-case bounds for the size of a planar
induced subgraph by showing that every graph (not necessarily triangle-free)
has an induced planar subgraph of n
m/ 5 . 2174 vertices and that there exist
graphs for which the largest induced planar subgraph is not much larger than
n
m/ 6 vertices.
1.1 New Results
We prove the following results:
Theorem 1. Every graph with n vertices and m edges has an induced pseudo-
forest with at least n
2 m
9
vertices.
Theorem 2. Every graph with n vertices and m edges has an induced subgraph
with treewidth at most 2 and with at least n
m
5
vertices.
Theorem 3. Every graph with n vertices and m edges has an induced planar
subgraph with treewidth at most 3 and with at least n
23 m
120
vertices.
These three theorems can be implemented as algorithms which take linear time
to find the induced subgraphs described by the theorems.
Theorem 4. For every integer h, there is a family of graphs such that for any
graph in this family with n vertices and m edges, the largest K h -minor-free in-
duced subgraph has at most n
m
m
6 + O (
log m ) vertices.
The bounds of Theorems 1 and 2 are tight, even for larger classes of induced
subgraphs. In particular, there exist graphs for which the largest induced outer-
planar subgraph has size at most n
m/ 4 . 5, so the bound of Theorem 1 is tight
for any class of graphs between the pseudoforests and the outerplanar graphs.
There also exist graphs for which the largest induced K 4 -free induced subgraph
has n
m/ 5 vertices, so Theorem 2 is tight for every family of graphs between
the treewidth 2 graphs and the graphs with no 4-clique.
1.2 Related Work
The worst-case size of the largest induced planar subgraph has been studied
previously by Edwards and Farr [7], who proved a tight bound of 3 n/ ( d +1)on
its size as a function of the maximum degree d of the given graph. In contrast, by
 
Search WWH ::




Custom Search