comparable-box-dimension.tex 63.6 KB
Newer Older
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
\newtheorem*{corollary-C}{Corollary~\ref{cor-tw}}
\begin{corollary-C}
Every graph $G$ satisfies $\cbdim(G)\le\tw(G)+1$.
\end{corollary-C}
\begin{proof}
Let $k=\tw(G)$.  Observe that there exists a $k$-tree $T$ with the root clique $C^\star$ such that $G\subseteq T-V(C^\star)$.
Inspection of the proof of Theorem~\ref{thm-ktree} (and Lemma~\ref{lem-cs}) shows that we obtain
a representation $h$ of $T-V(C^\star)$ in $\mathbb{R}^{k+1}$ such that
\begin{itemize}
\item the vertices are represented by hypercubes of pairwise different sizes,
\item if $uv\in E(T-V(C^\star))$ and $h(u)\sqsubseteq h(v)$, then $h(u)\cap h(v)$ is a facet of $h(u)$ incident
with its point with minimum coordinates, and
\item for each vertex $u$ and each facet of $h(u)$ incident with its point with minimum coordinates, there exists
at most one vertex $v$ such that $uv\in E(T-V(C^\star))$ and $h(u)\sqsubseteq h(v)$.
\end{itemize}
If for some $u,v\in V(G)$, we have $uv\in E(T)\setminus E(G)$, where without loss of generality $h(u)\sqsubseteq h(v)$,
Torsten Ueckerdt's avatar
Torsten Ueckerdt committed
1017
we now alter the representation by shrinking $h(u)$ slightly away from $h(v)$ (so that all other touchings are preserved).
1018
1019
1020
Since the hypercubes of $h$ have pairwise different sizes, the resulting touching representation of $G$ is by comparable boxes.
\end{proof}

Zdenek Dvorak's avatar
Zdenek Dvorak committed
1021
\end{document}
For faster browsing, not all history is shown. View entire blame