grid

• 2021/11 twinWidthI2021
  • page 15 : grid upper bounds twin-width by a constant – Theorem 4.3. For every positive integers $d$ and $n$, the $d$-dimensional $n$-grid has twin-width at most $3d$.
• 2010/08 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$.
• 2010 Jelinek2010
  • page 2 : graph class grid has unbounded rank-width – The grid $G_{n,n}$ has rank-width equal to $n-1$.
• 1998 Bodlaender1998
  • page 37 : graph class grid has unbounded treewidth – Lemma 88. The treewidth of an $n \times n$ grid graph … is at least $n$.
• unknown
  • graph class grid has unbounded distance to chordal
  • graph class grid has unbounded average distance
  • graph class grid has unbounded bisection bandwidth
  • grid upper bounds maximum degree by a constant
  • grid upper bounds maximum degree by a constant – By definition
• assumed
  • grid – Cartesian product of two paths.
  • grid upper bounds planar by a constant
  • graph class planar is not included in graph class grid
  • grid upper bounds bipartite by a constant
  • graph class bipartite is not included in graph class grid
  • grid upper bounds connected by a constant
  • graph class connected is not included in graph class grid
  • path upper bounds grid by a constant
  • graph class grid is not included in graph class path