Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms

1976/12/01 by Kellogg S. Booth, George S. Lueker · 18 citations
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Algorithm #Algorithms and Data Compression #Chordal graph #Combinatorics #Computer science #Discrete mathematics #Graph #Indifference graph #Interval (graph theory) #Interval graph #Line graph #Mathematics #Pathwidth #Planarity testing #Property (philosophy) #Property testing #Tree (set theory) #semigroups and automata theory

paper · doi:10.1016/s0022-0000(76)80045-1

crossref issued 1976/12/01 · crossref published 1976/12/01 · crossref published-print 1976/12/01 · openalex publication_date 1976/12/01 · crossref created 2010/10/15 · crossref deposited 2019/06/05 · openalex created_date 2025/10/10 · crossref indexed 2026/08/01 · openalex updated_date 2026/08/03

Citations

• Sur le problème des courbes gauches en Topologie
• Efficient Planarity Testing
• A Characterization of Comparability Graphs and of Interval Graphs
• Incidence matrices and interval graphs
• Optimal scheduling for two-processor systems

Cited by

• Unit disk graph recognition is NP-hard
• Crossing minimization in linear embeddings of graphs
• Achieving optimality for gate matrix layout and PLA folding: A graph theoretic approach
• The LBFS Structure and Recognition of Interval Graphs
• A simple test for interval graphs
• Classes of perfect graphs
• Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
• Two strikes against perfect phylogeny
• Parallel Algorithms in Graph Theory: Planarity Testing
• A Linear Recognition Algorithm for Cographs
• One-dimensional logic gate assignment and interval graphs
• Identification, Location-Domination and Metric Dimension on Interval and Permutation Graphs. II. Algorithms and Complexity
• On the problem of finding all maximum weight independent sets in interval and circular-arc graphs
• Fast algorithms for generating all maximal independent sets of interval, circular-arc and chordal graphs
• On Integrality, Stability and Composition of Dicycle Packings and Covers
• Arboricity and bipartite subgraph listing algorithms
• Twin-width VIIIa: Delineation
• Interval graph [wikipedia]