On the Linear MIM-width of Trees

Abstract

Linear MIM-width, and its generalization MIM-width, is a graph width parameter that has become noted for having bounded value on several important graph classes, e.g. interval graphs and permutation graphs. The linear MIM-width of a graph G measures a min-max relation on all maximum induced matchings in bipartite graphs given by a linear layout of the vertices in G, over all possible linear layouts. In this thesis we give an overlook of some of the research that has been done on this parameter, and provide a new result, computing the linear MIM-width of trees in n log n time.