Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs

Abstract

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. The complexity of recognizing 2-thin and proper 2-thin graphs is still open. In this work, we present characterizations of 2-thin and proper 2-thin graphs as intersection graphs of rectangles in the plane, as vertex intersection graphs of paths on a grid (VPG graphs), and by forbidden ordered patterns. We also prove that independent 2-thin graphs are exactly the interval bigraphs, and that proper independent 2-thin graphs are exactly the bipartite permutation graphs. Finally, we take a step towards placing the thinness and its variations in the landscape of width parameters, by upper bounding the proper thinness in terms of the bandwidth.

La delgadez de un grafo es un parámetro de anchura que generaliza algunas propiedades de los grafos de intervalo, que son exactamente los grafos de delgadez uno. Los grafos con delgadez a lo sumo dos incluyen, por ejemplo, los grafos convexos bipartitos. Muchos problemas NP-completos se pueden resolver en tiempo polinomial para grafos con delgadez acotada, dada una representación adecuada del grafo. La delgadez propia se define de forma análoga, generalizando los grafos de intervalo propios, y se sabe que una familia más grande de problemas NP-completos son resolubles polinomialmente para grafos con delgadez propia acotada. La complejidad de reconocer grafos 2-delgados y 2-delgados propios aún está abierta. En este trabajo, presentamos caracterizaciones de grafos 2-delgados y 2-delgados propios como grafos de intersección de rectángulos en el plano, como grafos de intersección de vértices de caminos en una cuadrícula (grafos VPG) y mediante patrones ordenados prohibidos. También demostramos que los grafos independientes 2-delgados son exactamente los bigrafos de intervalo, y que los grafos independientes propios 2-delgados son exactamente los grafos de permutación bipartitos. Finalmente, avanzamos hacia la ubicación de la delgadez y sus variaciones en el panorama de parámetros de ancho, acotando superiormente la delgadez propia en términos del ancho de banda.