Name
Title | ||
|---|---|---|
Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs |
Abstract | ||
|---|---|---|
We establish relations between the bandwidth and the treewidth of bounded degree graphs G, and relate these parameters to the size of a separator of G as well as the size of an expanding subgraph of G. Our results imply that if one of these parameters is sublinear in the number of vertices of G then so are all the others. This implies for example that graphs of fixed genus have sublinear bandwidth or, more generally, a corresponding result for graphs with any fixed forbidden minor. As a consequence we establish a simple criterion for universality for such classes of graphs and show for example that for each @c0 every n-vertex graph with minimum degree (34+@c)n contains a copy of every bounded-degree planar graph on n vertices if n is sufficiently large. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1016/j.ejc.2009.10.010 | Eur. J. Comb. |
Keywords | Field | DocType |
corresponding result,sublinear bandwidth,bounded degree graph,n vertex,simple criterion,n-vertex graph,bounded-degree planar graph,bounded-degree graph,minimum degree,fixed genus,planar graph | Discrete mathematics,Indifference graph,Combinatorics,Tree-depth,Partial k-tree,Clique-sum,Chordal graph,Treewidth,Pathwidth,1-planar graph,Mathematics | Journal |
Volume | Issue | ISSN |
31 | 5 | 0195-6698 |
Citations | PageRank | References |
18 | 0.98 | 14 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Julia Böttcher | 1 | 93 | 17.35 |
| Klaas P. Pruessmann | 2 | 94 | 11.00 |
| Anusch Taraz | 3 | 168 | 37.71 |
| Andreas Würfl | 4 | 25 | 3.23 |