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

Tabl e 1. Comparison of new and known results on induced subgraphs

Size of induced
subgraph

Additional
constraints

Type of subgraph Reference

n − m

independent set trivial

m
2

n − matching trivial

m
3

n − linear forest trivial

m
4

n − G is triangle-free forest [1]

m + c
4

n − max degree ≤ 3

c = # connected
components

forest [1]

n

max degree ʔ max degree 2 [10]

( ʔ +1) / 3

3 n
ʔ +5 / 3

max degree ʔ

outerplanar [16]

3 n
ʔ +1

max degree ʔ planar [7]

3 n
2 m/n +1

m ≥ 2 n or
connected and
m ≥ n

partial 2-tree [8]

5 n
6

claw-free subcubic planar partial 4-tree [5]

m
4 . 5

n − pseudoforest Theorem 1

m
5

n − partial 2-tree Theorem 2

m
5 . 2174

n − planar partial 3-tree Theorem 3

m
6 + o ( m )

≤ n − any minor-closed

property

Theorem 4

2-tree. A graph is a partial 2-tree if and only if every biconnected component
is a series parallel graph. The operations of adding a vertex with two adjacent
neighbors and of taking subgraphs preserve planarity, so every partial 2-tree and
every pseudoforest is a planar graph.
When constructing induced subgraphs of size n m/k , we will make the

simplifying assumption that our graph G has maximum degree at most

−

k − 1 .