  A theta is a graph formed by three paths between the same pair of distinct
vertices so that the union of any two of the paths induces a hole. A wheel is a
graph formed by a hole and a node that has at least 3 neighbors in the hole. In
this paper we obtain a decomposition theorem for the class of graphs that do
not contain an induced subgraph isomorphic to a theta or a wheel, i.e. the
class of (theta, wheel)-free graphs. The decomposition theorem uses clique
cutsets and 2-joins. Clique cutsets are vertex cutsets that work really well in
decomposition based algorithms, but are unfortunately not general enough to
decompose more complex hereditary graph classes. A 2-join is an edge cutset
that appeared in decomposition theorems of several complex classes, such as
perfect graphs, even-hole-free graphs and others. In these decomposition
theorems 2-joins are used together with vertex cutsets that are more general
than clique cutsets, such as star cutsets and their generalizations (which are
much harder to use in algorithms). This is a first example of a decomposition
theorem that uses just the combination of clique cutsets and 2-joins. This has
several consequences. First, we can easily transform our decomposition theorem
into a complete structure theorem for (theta, wheel)-free graphs, i.e. we show
how every (theta, wheel)-free graph can be built starting from basic graphs
that can be explicitly constructed, and gluing them together by prescribed
composition operations; and all graphs built this way are (theta, wheel)-free.
Such structure theorems are very rare for hereditary graph classes, only a few
examples are known. Secondly, we obtain an $\mathcal O (n^4m)$-time
decomposition based recognition algorithm for (theta, wheel)-free graphs.
Finally, in Parts III and IV of this series, we give further applications of
our decomposition theorem.
