Reducing prime graphs and recognizing circle graphs
From MaRDI portal
A reduction theorem for prime (simple) graphs in \textit{W. H. Cunningham}'s sense [SIAM J. Algebraic Discrete Methods 3, 214-228 (1982; Zbl 0497.05031)] is presented. It says that every prime graph of order \(n>5\) contains a smaller prime graph of order n-1. As an application a polynomial algorithm for recognizing circle graphs in \((n^ 5)\) time is presented.
Recommendations
Cites work
- A characterization of circle graphs
- Connectivity in Matroids
- Decomposition of Directed Graphs
- Graph theory with applications
- Graphic presentations of isotropic systems
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 3933116 (Why is no real title available?)
- scientific article; zbMATH DE number 3750970 (Why is no real title available?)
- scientific article; zbMATH DE number 3588700 (Why is no real title available?)
- scientific article; zbMATH DE number 3361902 (Why is no real title available?)
- Isotropic systems
- Lectures on matroids
- Recognizing circle graphs in polynomial time
- Reconnaissance des graphes de cordes
Cited in
(64)- Graph theoretic approach to parallel gene assembly
- Circle graphs and the cycle double cover conjecture
- Isotropic systems
- Graphic presentations of isotropic systems
- Representations of graphs and networks (coding, layouts and embeddings)
- Thresholds for classes of intersection graphs
- Classes and recognition of curve contact graphs
- Minimally 3-connected isotropic systems
- Connectivity and \(\beta\)-invariants of isotropic systems and 4-regular graphs
- Covering and coloring polygon-circle graphs
- A proof of a circle graph characterization
- Container ship stowage problem complexity and connection to the coloring of circle graphs
- FO model checking on geometric graphs
- Linear rank-width of distance-hereditary graphs II. vertex-minor obstructions
- On a Hopf algebra in graph theory
- On edge transitivity of directed graphs
- A 2-isomorphism theorem for delta-matroids
- Forbidden induced subgraph characterization of circle graphs within split graphs
- Rank connectivity and pivot-minors of graphs
- Topology and counting of real algebraic curves
- 2-nested matrices: towards understanding the structure of circle graphs
- Isotropic matroids. III: Connectivity
- On polygon numbers of circle graphs and distance hereditary graphs
- Interlacement and activities in delta-matroids
- Counting hexagonal patches and independent sets in circle graphs
- Structural results on circular-arc graphs and circle graphs: a survey and the main open problems
- Mutant knots and intersection graphs
- Contact representations of planar graphs: extending a partial representation is hard
- Parallel algorithms for maximal cliques in circle graphs and unrestricted depth search
- Digraphs of bounded width
- Notes on a theorem of Naji
- The Pure Prime Circle Orbit Conjecture
- Weighted interlace polynomials
- scientific article; zbMATH DE number 3933116 (Why is no real title available?)
- Digraph Decompositions and Eulerian Systems
- Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs
- Practical and efficient circle graph recognition
- Practical and efficient split decomposition via graph-labelled trees
- The transition matroid of a 4-regular graph: an introduction
- Coloring graphs without fan vertex-minors and graphs without cycle pivot-minors
- The complexity of colouring circle graphs (extended abstract)
- FO model checking of geometric graphs
- Distance Hereditary Graphs and the Interlace Polynomial
- scientific article; zbMATH DE number 2230199 (Why is no real title available?)
- From matrix pivots to graphs in surfaces: exploring combinatorics through partial duals
- Circle graph isomorphism in almost linear time
- A chain theorem for sequentially 3-rank-connected graphs with respect to vertex-minors
- Prime vertex-minors of a prime graph
- Partial characterizations of circle graphs
- Vertex-minors of graphs: a survey
- Extending partial representations of circle graphs in near-linear time
- Word-representability of graphs with respect to split recomposition
- On the linear algebra of local complementation
- Simultaneous contact representations of planar graphs
- Recognizing locally equivalent graphs
- Characterization of double-arborescences and their minimum length word-representants
- Counting graphs induced by Gauss diagrams and families of mutant alternating knots
- Splitting cubic circle graphs
- Isotropic matroids. II: Circle graphs
- A new simple algorithm for computing maximum weight induced forests in circle graphs
- Unavoidable vertex-minors in large prime graphs
- Circle graphs and monadic second-order logic
- Diamond-free circle graphs are Helly circle
- \(O(m\log n)\) split decomposition of strongly-connected graphs
This page was built for publication: Reducing prime graphs and recognizing circle graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1116953)
