Incidence matrices and interval graphs

Abstract

According to present genetic theory, the fine structure of genes consists of linearly ordered elements.A mutant gene is obtained by alteration of some connected portion of this structure.By examining data obtained from suitable experiments, it can be determined whether or not the blemished portions of two mutant genes intersect or not, and thus intersection data for a large number of mutants can be represented as an undirected graph.If this graph is an "interval graph," then the observed data is consistent with a linear model of the gene.The problem of determining when a graph is an interval graph is a special case of the following problem concerning (0, l)-matrices: When can the rows of such a matrix be permuted so as to make the l's in each column appear consecutively?A complete theory is obtained for this latter problem, culminating in a decomposition theorem which leads to a rapid algorithm for deciding the question, and for constructing the desired permutation when one exists.Let A -(dij) be an m by n matrix whose entries a i3 are all either 0 or 1.The matrix A may be regarded as the incidence matrix of elements e l9 e 2 , , e m vs. sets S l9 S 2 , , S n ; that is, a i3 = 0 or 1 according as e t is not or is a member of S 3 .For certain applications, one of which will be discussed below, it is of interest to know whether or not one can order the elements in such a way that each set S 3 consists of elements that appear consecutively in the ordering.In terms of the incidence matrix A, the question is whether there is an m by m permutation matrix P such that the Γs in each column of PA occur in consecutive positions.We shall describe a computationally efficient method of answering this question, and of determining such a P when one exists.Given a family of sets S lf S 29 , S n , one can form the intersection graph of the family by associating a vertex of the graph with each set and joining two distinct vertices with an edge if their corresponding sets have a nonempty intersection.Conversely, any finite graph can of course be viewed as the intersection graph of a family of sets (in many ways).If each set can be taken as an interval on the real line, the graph is called an interval graph.Interval graphs have been investigated in [7,5,3].The problem posed above is closely related to that of determining whether a given graph is an interval