Name
Abstract | ||
|---|---|---|
We prove that planar graphs with bounded maximum degree have sublinear bandwidth. As a consequence for each γ>0 every n-vertex graph with minimum degree (34+γ)n contains a copy of every bounded-degree planar graph on n vertices. The proof relies on the fact that planar graphs have small separators. Indeed, we show more generally that for any class of bounded-degree graphs the concepts of sublinear bandwidth, sublinear treewidth, the absence of big expanders as subgraphs, and the existence of small separators are equivalent. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1016/j.endm.2008.06.018 | Electronic Notes in Discrete Mathematics |
Keywords | Field | DocType |
maximum degree,planar graph | Discrete mathematics,Outerplanar graph,Combinatorics,Partial k-tree,Chordal graph,Clique-sum,Treewidth,Pathwidth,1-planar graph,Mathematics,Planar graph | Journal |
Volume | ISSN | Citations |
31 | 1571-0653 | 1 |
PageRank | References | Authors |
0.36 | 5 | 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 |