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

Kellogg S. Booth; George S. Lueker

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

Keywords

Planarity testingChordal graphInterval graphAlgorithmCombinatoricsMathematicsProperty testingProperty (philosophy)Tree (set theory)Indifference graphInterval (graph theory)GraphPathwidthDiscrete mathematicsComputer science1-planar graphLine graph

Affiliated Institutions

Related Publications

Random graphs with arbitrary degree distributions and their applications

M. E. J. Newman , Steven H. Strogatz , Duncan J. Watts

Recent work on the structure of social networks and the internet has focused attention on graphs with distributions of vertex degree that are significantly different from the Po...

2001 Physical review. E, Statistical physi... 3631 citations

Covariance selection for nonchordal graphs via chordal embedding

Joachim Dahl , Lieven Vandenberghe , Vwani Roychowdhury

We describe algorithms for maximum likelihood estimation of Gaussian graphical models with conditional independence constraints. This problem is also known as covariance selecti...

2008 Optimization methods & software 117 citations

Pattern vectors from algebraic graph theory

Richard C. Wilson , Edwin R. Hancock , Bin Luo

Graph structures have proven computationally cumbersome for pattern analysis. The reason for this is that, before graphs can be converted to pattern vectors, correspondences mus...

2005 IEEE Transactions on Pattern Analysis... 218 citations

Analytic and Algorithmic Solution of Random Satisfiability Problems

Marc Mézard , Giorgio Parisi , Riccardo Zecchina

We study the satisfiability of random Boolean expressions built from many clauses with K variables per clause (K-satisfiability). Expressions with a ratio α of clauses to variab...

2002 Science 1038 citations

Chemical Graph Theory

Nenad Trinajstić

INTRODUCTION. ELEMENTS OF GRAPH THEORY. The Definition of a Graph. Isomorphic Graphs and Graph Automorphism. Walks, Trails, Paths, Distances and Valencies in Graphs. Subgraphs. ...

2018 1459 citations

Publication Info

Year: 1976
Type: article
Volume: 13
Issue: 3
Pages: 335-379
Citations: 1482
Access: Closed

External Links

View on DOI.org

Social Impact

Altmetric

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

PlumX Metrics

Social media, news, blog, policy document mentions

Citation Metrics

1482

OpenAlex

Cite This

APA Style

                            
                                    Kellogg S. Booth, 
                                
                                    George S. Lueker
                                
                            (1976). 
                            Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. 
                            Journal of Computer and System Sciences
                            , 13
                            (3)
                            , 335-379.
                            https://doi.org/10.1016/s0022-0000(76)80045-1

Identifiers

DOI: 10.1016/s0022-0000(76)80045-1