Incidence matrices and interval graphs

1965/09/01 by D. R. Fulkerson, Delbert Fulkerson, Oliver Gross · 31 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Combinatorics #DNA and Biological Computing #Evolutionary Algorithms and Applications #Geometry #Incidence (geometry) #Incidence matrix #Interval (graph theory) #Mathematics

paper · pdf · doi:10.2140/pjm.1965.15.835

crossref issued 1965/09/01 · crossref published 1965/09/01 · crossref published-print 1965/09/01 · openalex publication_date 1965/09/01 · crossref created 2012/11/30 · crossref deposited 2017/03/11 · openalex created_date 2025/10/10 · crossref indexed 2026/07/31 · openalex updated_date 2026/08/01

Abstract

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, 1)-matrices: When can the rows of such a matrix be permuted so as to make the 1's in each colum 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.

Citations

• Classes of recursive functions based on Ackermann’s function

Cited by

• Unit disk graph recognition is NP-hard
• Approximating treewidth and pathwidth of some classes of perfect graphs
• Dominoes
• Inapproximability of Treewidth and Related Problems
• The k-in-a-Path Problem for Claw-free Graphs
• Positional Identifiability from Pairwise Collision Data
• Complexity and algorithms for reasoning about time
• On the Classes of Interval Graphs of Limited Nesting and Count of Lengths
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• A simple test for interval graphs
• Decomposition by clique separators
• Trivially perfect graphs
• Generating and characterizing the perfect elimination orderings of a chordal graph
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Subexponential Parameterized Algorithm for Minimum Fill-In
• Two strikes against perfect phylogeny
• Recognizing Chordal Probe Graphs and Cycle-Bicolorable Graphs
• Fast parallel algorithms for chordal graphs
• One-dimensional logic gate assignment and interval graphs
• Fast algorithms for generating all maximal independent sets of interval, circular-arc and chordal graphs
• A Linear Time Algorithm for Deciding Interval Graph Isomorphism
• Layout of Graphs with Bounded Tree-Width
• A Recursive Characterization of Laplacian Spectral Radii of Trees with Bounded Maximum Degree
• Proving a conjecture on chromatic polynomials by counting the number of acyclic orientations
• Constructing Adjacency Arrays from Incidence Arrays
• Estimating high-dimensional intervention effects from observational data
• Characterization of the graphs with boxicity ⩽2
• Intransitive indifference with unequal indifference intervals
• Chordal graph [wikipedia]
• Interval graph [wikipedia]