On the thinness of trees

Abstract

The study of structural graph width parameters like tree-width, clique-width and rank-width has been ongoing during the last five decades, and their algorithmic use has also been increasing (Cygan et al., 2015). New width parameters continue to be defined, for example, MIM-width in 2012, twin-width in 2020, and mixed-thinness, a generalization of thinness, in 2022.The concept of thinness of a graph was introduced in 2007 by Mannino, Oriolo, Ricci and Chandran, and it can be seen as a generalization of interval graphs, which are exactly the graphs with thinness equal to one. This concept is interesting because if a representation of a graph as a k-thin graph is given for a constant value k, then several known NP-complete problems can be solved in polynomial time. Some examples are the maximum weighted independent set problem, solved in the seminal paper by Mannino et al., and the capacitated coloring with fixed number of colors (Bonomo, Mattia and Oriolo, 2011).In this work we present a constructive O(nlog(n))-time algorithm to compute the thinness for any given n-vertex tree, along with a corresponding thin representation. We use intermediate results of this construction to improve known bounds of the thinness of some special families of trees.