On embedding graphs in trees
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).
- A framework for solving VLSI graph layout problems
- A variation on the min cut linear arrangement problem
- Better expanders and superconcentrators
- Complexity of Finding Embeddings in a k-Tree
- Cost Trade-offs in Graph Embeddings, with Applications
- Graph minors. I. Excluding a forest
- Graph minors. III. Planar tree-width
- Graph minors. V. Excluding a planar graph
- Graph minors. VI. Disjoint paths across a disc
- Graph minors. X: Obstructions to tree-decomposition
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 3813518 (Why is no real title available?)
- The bandwidth problem for graphs and matrices—a survey
- Topological Bandwidth
- Upper and Lower Bounds on the Complexity of the Min-Cut Linear Arrangement Problem on Trees
- On spanning tree congestion of graphs
- On spanning tree congestion
- Precoloring extension. I: Interval graphs
- Embedding meshes of trees into deBruijn graphs
- On the complexity of tree embedding problems
- On optimal embeddings and trees
- Minimal congestion trees
- Embedding trees in recursive circulants
- Near-optimal lower bounds on regular resolution refutations of Tseitin formulas for all constant-degree graphs
- Treewidth, crushing and hyperbolic volume
- Two-page book embedding of trees under vertex-neighborhood constraints
- Embeddings and other mappings of rooted trees into complete trees
- Towards optimal embedding of an arbitrary tree in a graceful tree
- Perfect trees and elementary embeddings
- scientific article; zbMATH DE number 5556284 (Why is no real title available?)
- Cost Trade-offs in Graph Embeddings, with Applications
- scientific article; zbMATH DE number 125491 (Why is no real title available?)
- Embedding an arbitrary binary tree into the star graph
- Embedding of cycles and wheels into arbitrary trees
- Parameterization of tensor network contraction
- scientific article; zbMATH DE number 7236450 (Why is no real title available?)
- scientific article; zbMATH DE number 6297807 (Why is no real title available?)
- Embedding of K_r+K^c_s and K_r+P_s into arbitrary trees
- Optimal arrangement of data in a tree directory
- Minimum average congestion of enhanced and augmented hypercubes into complete binary trees
- Tree-layout based graph classes: proper chordal graphs
- Cuts, trees and \(\ell_1\)-embeddings of graphs
- Parameterized complexity of quantum knot invariants
- The treewidth of line graphs
- On tree congestion of graphs
This page was built for publication: On embedding graphs in trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1103631)
