The "thinness" of a graph is an invariant presented as a generalization of interval graphs, which are exactly the graphs with thinness equal to one. If a representation of a graph as a k-thin graph is given for a constant value k, then some known NP-complete problems can be solved in polynomial time. Some examples are the maximum weighted independent set problem and the bounded coloring with fixed number of colors.

In this work we present a constructive O(n log n)-time algorithm to compute the thinness for any given tree, along with an optimal consistent solution (ordering and partition). We use some intermediate results of this construction to improve known bounds of the thinness in some special trees.