\begin{theorem} \label{thm:chor_sub_size_xp}
The problem $\ext(\chor,\sub)$ is in \cXP\ with respect to $b$ where $b$ is the
number of branch vertices of $T$.
\end{theorem}

\begin{proof}
The chordal graph $G$ has at most $\O(n+m)$ maximal cliques which we can find in
linear time~\cite{recog_chordal_graphs}. Now each maximal clique has at least
one private vertex in a tree.  We test all possible mappings $f$ of the
branch-vertices of the tree to the maximal cliques, there are at most $(n+m)^b$
such mappings (and of course the mapping has to agree with the partial
representation).

Now, we know the structure on the branch vertices and we need to create the
structure in between branch vertices which corresponds to extending interval
graphs. Two branch vertices are called \emph{neighbors} if they are connected by
path in $T$ having all inner vertices of degree two. We create a graph $B$ whose
vertices are the branch vertices of $T$ and $uv \in E(B)$ if and only if $u$ and
$v$ are neighbors in $T$. 

First we deal with unlocated components. There are two possibilities where to
place them. If none is possible and there are unlocated components, then the
constructed mapping $f$ is not correct.
\begin{packed_enum}
\item Let $uv \in E(B)$. If $f(u)$ and $f(v)$ are maximum cliques belonging to
the same component of $G$, the entire subdivided path between $u$ and
$v$ in $T$ is taken by this component. If $f(u)$ and $f(v)$ belong to
different components, the components are meeting in the middle and by
subdividing there is enough space to place all unlocated components.
\item The other possiblity is to place unlocated components around a leaf of
$T$. Let $x \in T$ be a leaf and $y \in T$ be the branch-vertex to which
the path from $x$ is attached. If either $x$ is not taken by any
pre-drawn interval or the pre-drawn interval containing $x$ belongs to a
different component then $f(y)$, it is again possible to place all
unlocated components here.
\end{packed_enum}

Now, to deal with located components, we need to distribute the vertices to the
paths of $T$ belonging to neighboring branch vertices. {\tt TODO: Related to
clique cover of a comparability graph}. 
\end{proof}

The above results can be stated in a different perspective. Let $H$ be a fixed
graph. We can define two classes of intersection graphs in $H$. A class of all
intersection graphs of connected subgraphs of $H$ is denoted by \hfixed{H}. A
class of all intersection graphs of connected subgraphs of a subdivision of $H$
is denoted by \hsub{H}. So $\hsub{H} = \bigcup_{H'} \hfixed{H'}$; union for all
subdivisions $H'$ of $H$. Also, for these classes, we can consider partial
representation extension problem.

A straightforward generalization of Theorem~\ref{thm:hfixed} states that
extension of the classes \hfixed{H} is fixed parameter tractable with respect to
$|H|$.  If $H$ is a tree $T$, the class \hsub{T} is a subclass of \chor; it
contains all chordal graphs representable inside of a tree of given fixed
structure. Theorem~\ref{thm:chor_sub_size_xp} can be restated in the following
way:

\begin{corollary}
For every fix tree $T$, the class \hsub{T} can be extended in a polynomial time
$\O((n+m)^b)$ where $b$ is the number of branch vertices of $T$. 
\end{corollary}
 
