On embedding graphs in trees
type: Item
instance of: scholarly article
title: On embedding graphs in trees
zbMATH Open document ID: 0646.05025
DOI: 10.1016/0095-8956(90)90066-9
published in: Journal of Combinatorial Theory. Series B
publication date: 1990-01-01T00:00:00Z
review text: 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).
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 4053645
zbMATH Keywords: chordal graph
zbMATH Keywords: graph minors
zbMATH Keywords: tree-width
zbMATH Keywords: graph embeddings
author: Daniel Bienstock
MaRDI profile type: Publication
full work available at URL: 0095-8956(90)90066-9
OpenAlex ID: W2012917738
cites work: Complexity of Finding Embeddings in a k-Tree
cites work: Better expanders and superconcentrators
cites work: A framework for solving VLSI graph layout problems
cites work: The bandwidth problem for graphs and matrices—a survey
cites work: Q3328583
cites work: Cost Trade-offs in Graph Embeddings, with Applications
cites work: Upper and Lower Bounds on the Complexity of the Min-Cut Linear Arrangement Problem on Trees
cites work: Q3661483
cites work: Topological Bandwidth
cites work: Graph minors. I. Excluding a forest
cites work: Graph minors. III. Planar tree-width
cites work: Graph minors. X: Obstructions to tree-decomposition
cites work: Graph minors. V. Excluding a planar graph
cites work: Graph minors. VI. Disjoint paths across a disc
cites work: A variation on the min cut linear arrangement problem
description: scientific article; zbMATH DE number 4053645