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