On embedding graphs in trees

DOI10.1016/0095-8956(90)90066-9zbMath0646.05025OpenAlexW2012917738MaRDI QIDQ1103631

Bienstock, Daniel

Publication date: 1990

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0095-8956(90)90066-9

zbMATH Keywords

chordal graphgraph embeddingstree-widthgraph minors

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items (11)

Minimal congestion trees ⋮ Minimum average congestion of enhanced and augmented hypercubes into complete binary trees ⋮ Near-optimal lower bounds on regular resolution refutations of Tseitin formulas for all constant-degree graphs ⋮ Precoloring extension. I: Interval graphs ⋮ Unnamed Item ⋮ Optimal arrangement of data in a tree directory ⋮ Treewidth, crushing and hyperbolic volume ⋮ The treewidth of line graphs ⋮ Unnamed Item ⋮ On spanning tree congestion of graphs ⋮ On spanning tree congestion

Cites Work

• Unnamed Item
• Unnamed Item
• A framework for solving VLSI graph layout problems
• Graph minors. III. Planar tree-width
• Graph minors. I. Excluding a forest
• Graph minors. VI. Disjoint paths across a disc
• Graph minors. V. Excluding a planar graph
• Graph minors. X: Obstructions to tree-decomposition
• Topological Bandwidth
• Complexity of Finding Embeddings in a k-Tree
• Cost Trade-offs in Graph Embeddings, with Applications
• Better expanders and superconcentrators
• A variation on the min cut linear arrangement problem
• Upper and Lower Bounds on the Complexity of the Min-Cut Linear Arrangement Problem on Trees
• The bandwidth problem for graphs and matrices—a survey

This page was built for publication: On embedding graphs in trees