## Abstract

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)^{3}), 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^{2} (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^{2}(n)(d^{2} + log(n) log log^{2} (n))).

Original language | English |
---|---|

Pages (from-to) | 17-50 |

Number of pages | 34 |

Journal | Journal of Algorithms |

Volume | 43 |

Issue number | 1 |

DOIs | |

State | Published - Apr 2002 |

## Keywords

- Binary tree
- Dynamic embedding
- Hypercube
- Simulation of algorithms