Embedding Graphs with Bounded Treewidth into Optimal Hypercubes
In this paper, we present a one-to-one embedding of a graph with
bounded treewidth into its optimal hypercube.
This is the first time that embeddings of graphs with a very
irregular structure into hypercubes are investigated.
The dilation of the presented embedding is bounded by
3*ceil(log((d+1)(t+1)))+8, where t denotes the treewidth of the graph
and d denotes the maximal degree of a vertex in the graph.
The given embedding is a generalization of our method to embed
arbitrary binary trees into their optimal hypercubes given in
[Heun-Mayr/TUM-I9321].
Moreover, if the given graph has constant treewidth or is represented
by a tree-decomposition of width t, this embedding can be efficiently
implemented on the optimal hypercube itself.
