On the Twin-width of Outerplanar Graphs
摘要
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.