The proper thinness of a graph is an invariant that generalizes the concept of a proper interval graph. Every graph has a numerical value of proper thinness and the graphs with proper thinness 1 are exactly the proper interval graphs. A graph is proper k -thin if its vertices can be ordered in such a way that there is a partition of the vertices into k classes satisfying that for each triple of vertices r < s < t , such that there is an edge between r and t , it is true that if r and s belong to the same class, then there is an edge between s and t , and if s and t belong to the same class, then there is an edge between r and s . The proper thinness is the smallest value of k such that the graph is proper k -thin. In this work we focus on the calculation of proper thinness for trees. We characterize trees of proper thinness 2, both structurally and by their minimal forbidden induced subgraphs. The characterizations obtained lead to a polynomial-time recognition algorithm. We furthermore show why the structural results obtained for trees of proper thinness 2 cannot be straightforwardly generalized to trees of proper thinness 3.

A bipartite graph G=(A,B,E) is H-convex for some family of graphs H if there exists a graph H∈H with V(H)=A such that the neighbours in A of each b∈B induce a connected subgraph of H. Many NP-complete problems are polynomial-time solvable for H-convex graphs when H is the set of paths. The underlying reason is that the class has bounded mim-width. We extend this result to families of H-convex graphs where H is the set of cycles, or H is the set of trees with bounded maximum degree and a bounded number of vertices of degree at least 3. As a consequence, we strengthen many known results via one general and short proof. We also show that the mim-width of H-convex graphs is unbounded if H is the set of trees with arbitrarily large maximum degree or an arbitrarily large number of vertices of degree at least 3.

The thinness of a graph is a width parameter that generalizes some properties of interval graphs, which are exactly the graphs of thinness one. Graphs with thinness at most two include, for example, bipartite convex graphs. Many NP-complete problems can be solved in polynomial time for graphs with bounded thinness, given a suitable representation of the graph. Proper thinness is defined analogously, generalizing proper interval graphs, and a larger family of NP-complete problems are known to be polynomially solvable for graphs with bounded proper thinness. It is known that the thinness of a graph is at most its pathwidth plus one. In this work, we prove that the proper thinness of a graph is at most its bandwidth, for graphs with at least one edge. It is also known that boxicity is a lower bound for the thinness. The main results of this work are characterizations of 2-thin and 2-proper thin graphs as intersection graphs of rectangles in the plane with sides parallel to the Cartesian axes and other specific conditions. We also bound the bend number of graphs with low thinness as vertex intersection graphs of paths on a grid (Bk-VPG graphs are the graphs that have a representation in which each path has at most k bends). We show that 2-thin graphs are a subclass of B1-VPG graphs (moreover, of L-graphs, that is, B1-VPG graphs admitting a representation that uses only one of the four possible shapes ⌊,⌋⌈,⌉), and that 3-thin graphs are a subclass of B3-VPG graphs. We also show that B0-VPG graphs may have arbitrarily large thinness, and that not every 4-thin graph is a VPG graph.