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.     «

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...     »