Embedding graphs with bounded treewidth into their 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 highly irregular structure into hypercubes are investigated. The presented embedding achieves dilation of at most 3⌈log((d + 1)(t + 1))⌉ + 8 and node-congestion of at most O(d(dt)³), where t denotes the treewidth of the graph and d denotes the maximal degree of a vertex in the graph. Provided that the graph is given by its tree-decomposition the embedding can be computed efficiently on the hypercube itself. In particular, the embedding of a graph with constant treewidth and constant degree can be computed in time O(log² (n) log log log(n)*(n)). For graphs with constant treewidth, a minimal tree-decomposition can be computed efficiently in parallel due to a result of Bodlaender and Hagerup. In this case, the embedding can be computed on the hypercube in time O(log²(n)(d² + log(n) log log² (n))).