grid

• unknown source
  • graph class grid has unbounded distance to chordal
  • graph class grid has unbounded average distance
  • graph class grid has unbounded bisection bandwidth
  • graph class grid has constant maximum degree
• assumed
  • grid – Cartesian product of two paths.
  • graph class grid is included in graph class planar
  • graph class planar is not included in graph class grid
  • graph class grid is included in graph class bipartite
  • graph class bipartite is not included in graph class grid
  • graph class grid is included in graph class connected
  • graph class connected is not included in graph class grid
  • graph class path is included in graph class grid
  • graph class grid is not included in graph class path
  • graph class grid has constant maximum degree – By definition
• twinWidthI2021
  • page 15 : graph class grid has constant twin-width – Theorem 4.3. For every positive integers $d$ and $n$, the $d$-dimensional $n$-grid has twin-width at most $3d$.
• Jelinek2010
  • page 2 : graph class grid has unbounded rank-width – The grid $G_{n,n}$ has rank-width equal to $n-1$.
• Bodlaender1998
  • page 37 : graph class grid has unbounded treewidth – Lemma 88. The treewidth of an $n \times n$ grid graph … is at least $n$.
• Sasak2010
  • page 17 : graph class grid has unbounded treewidth – Theorem 2.4
  • page 32 : graph class grid has unbounded treedepth – Corollary 2.24 Tree-depth of a grid is at least $\lceil \log_2(n+1)\rceil$.