Twin-width is a recently introduced graph parameter that measures the similarity of a graph to a cograph. It is analogous to treewidth, which measures how similar a graph to a tree is. Many NP-hard problems are fixed-parameter tractable on graphs with bounded treewidth or twin-width. Twin-width is proven as a more general width parameter as it is bounded for all bounded treewidth graphs and beyond. For example, the treewidth and twin-width for planar graphs are \(O(\sqrt{n})\) and at most 8, respectively. Nonetheless, the twin-width bound for planar graphs is yet to be proven tight, and very little is known about the subclasses of planar graphs. In this paper, we focus on obtaining the tight bound of the twin-width of outerplanar graphs, a well-known subclass of planar graphs. We show that every outerplanar graph has twin-width at most 3, and there is an outerplanar graph with twin-width at least 3.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On the Twin-width of Outerplanar Graphs

  • Muhammad Anwarul Azim,
  • Sk Ruhul Azgor,
  • Sadia Sharmin,
  • Md. Saidur Rahman

摘要

Twin-width is a recently introduced graph parameter that measures the similarity of a graph to a cograph. It is analogous to treewidth, which measures how similar a graph to a tree is. Many NP-hard problems are fixed-parameter tractable on graphs with bounded treewidth or twin-width. Twin-width is proven as a more general width parameter as it is bounded for all bounded treewidth graphs and beyond. For example, the treewidth and twin-width for planar graphs are \(O(\sqrt{n})\) and at most 8, respectively. Nonetheless, the twin-width bound for planar graphs is yet to be proven tight, and very little is known about the subclasses of planar graphs. In this paper, we focus on obtaining the tight bound of the twin-width of outerplanar graphs, a well-known subclass of planar graphs. We show that every outerplanar graph has twin-width at most 3, and there is an outerplanar graph with twin-width at least 3.