linear NLC-width

• 2005 Gurski2005
  • page 4 : linear NLC-width – Definition 3
  • page 8 : linear NLC-width $k$ upper bounds NLCT-width by $\mathcal O(k)$
  • page 8 : pathwidth $k$ upper bounds linear NLC-width by $f(k)$ – The results of [23] imply that each graph class of bounded path-width has bounded linear NLC-width and that each graph class of bounded tree-width has bounded NLCT-width.
• 1998 Johansson1998
  • linear clique-width $k$ upper bounds linear NLC-width by $\mathcal O(k)$
  • linear NLC-width $k$ upper bounds linear clique-width by $\mathcal O(k)$