  We develop a framework for applying treewidth-based dynamic programming on
graphs with "hybrid structure", i.e., with parts that may not have small
treewidth but instead possess other structural properties. Informally, this is
achieved by defining a refinement of treewidth which only considers parts of
the graph that do not belong to a pre-specified tractable graph class. Our
approach allows us to not only generalize existing fixed-parameter algorithms
exploiting treewidth, but also fixed-parameter algorithms which use the size of
a modulator as their parameter. As the flagship application of our framework,
we obtain a parameter that combines treewidth and rank-width to obtain
fixed-parameter algorithms for Chromatic Number, Hamiltonian Cycle, and
Max-Cut.
