1 Computing the minimum rank of partial 2trees

By Hein van der Holst.

A 2-tree is recursively defined as follows: the complete graph on three vertices is a 2-tree, and if we have a 2-tree, a larger can be obtained by adding a new vertex adjacent to the endpoints of an edge in the 2-tree. A partial 2-tree is a subgraph of a 2-tree. The minimum rank of a graph G is the smallest rank over all symmetric matrices A = [a_{i,j}] with a_{i,j} ≠ 0, i ≠ j if and only if ij is an edge of G. In this talk, I present an efficient algorithm to compute the minimum rank of a partial 2-tree, and show how it can be extended to compute other minimum rank-type problems.