Name
Abstract | ||
|---|---|---|
Many graph parameters of grid-like graphs are studied because of their algorithmic consequences. An important concept in this context is that of treewidth. Treewidth of graphs is a graph parameter for measuring how close a graph is to a tree. In this paper, we study the treewidth of toroidal grids and show that the treewidth of the n×n toroidal grid is either 2n−2 or 2n−1. We then show that these bounds are tight in some cases. To show the lower bounds, we construct brambles of high orders. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1016/j.dam.2015.06.027 | Discrete Applied Mathematics |
Keywords | Field | DocType |
Treewidth,Toroidal grid,Bramble | Discrete mathematics,Combinatorics,Tree-depth,Partial k-tree,Tree decomposition,Clique-sum,Chordal graph,Clique-width,Treewidth,1-planar graph,Mathematics | Journal |
Volume | Issue | ISSN |
198 | C | 0166-218X |
Citations | PageRank | References |
0 | 0.34 | 12 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Masashi Kiyomi | 1 | 204 | 17.45 |
| Yoshio Okamoto | 2 | 170 | 28.50 |
| Yota Otachi | 3 | 161 | 37.16 |