grid

equivalent to: grid

providers: ISGCI

Relations

Results

• 2021 Twin-width I: Tractable FO Model Checking by Bonnet, Kim, Thomassé, Watrigant
  • 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$.
• 2010 Comparing 17 graph parameters by Sasák
  • 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 The rank-width of the square grid by Jelínek
  • page 2 : graph class grid has unbounded rank-width – The grid $G_{n,n}$ has rank-width equal to $n-1$.
• 1998 A partial $k$-arboretum of graphs with bounded treewidth by Bodlaender
  • page 37 : graph class grid has unbounded treewidth – Lemma 88. The treewidth of an $n \times n$ grid graph … is at least $n$.
• 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