On embedding graphs in trees (Q1103631)

Let G be a graph of small maximum degree, which is contained in a chordal graph of small clique number. Is G then contained in a chordal graph of small maximum degree as well? This extremal problem arises from the following: suppose we seek a binary tree T and an injective mapping from V(G) to V(T) (and which sends edges of G to paths in T) so that we minimize (1) The maximum overlap, over any edge of T, of paths corresponding to edges of G (known as congestion), or (2) The maximum, over all edges of G, of the length of the corresponding path in T (known as dilation). We show that the congestion is controlled by the maximum degree of G and its tree-width. It is in comparing congestion and dilation that the chordal graph problem arises. The answer is ``yes'' for graphs of small genus, and ``nearly yes'' for all graphs (the dependence of the best maximum degree on the number of vertices of G is at worst very weak).