@inproceedings{05bf992e87b343eab28bb22fbccb0fbf,
title = "Embedding graphs with bounded treewidth into optimal hypercubes",
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 very irregular structure into hypercubes are investigated. The dilation of the presented embedding is bounded by 3 [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. Moreover, if the 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.",
author = "Volker Heun and Mayr, \{Ernst W.\}",
note = "Publisher Copyright: {\textcopyright} 1996, Springer Verlag. All rights reserved.; 13th Annual Symposium on Theoretical Aspects of Computer Science, STACS 1996 ; Conference date: 22-02-1996 Through 24-02-1996",
year = "1996",
doi = "10.1007/3-540-60922-9\_14",
language = "English",
isbn = "9783540609223",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "155--168",
editor = "Claude Puech and Rudiger Reischuk",
booktitle = "STACS 1996 - 13th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings",
}