Circle graphs and monadic second-order logic

DOI10.1016/j.jal.2007.05.001zbMath1149.03011OpenAlexW1975250030MaRDI QIDQ946577

Bruno Courcelle

Publication date: 23 September 2008

Published in: Journal of Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jal.2007.05.001

zbMATH Keywords

monadic second-order logicchord diagramcircle graphsplit decompositionmonadic second-order transductionorder-invariant monadic second-order property

Mathematics Subject Classification ID

Related Items (12)

Notes on a theorem of Naji ⋮ From matrix pivots to graphs in surfaces: exploring combinatorics through partial duals ⋮ Semi-transitive orientations and word-representable graphs ⋮ Practical and efficient circle graph recognition ⋮ Mutant knots and intersection graphs ⋮ Weighted Interlace Polynomials ⋮ Diamond-free circle graphs are Helly circle ⋮ A 2-isomorphism theorem for delta-matroids ⋮ Splitting cubic circle graphs ⋮ The complexity of the vertex-minor problem ⋮ Alternation Graphs ⋮ Symbol Separation in Double Occurrence Words

Cites Work

• Algorithmic uses of the Feferman-Vaught theorem
• Elements of finite model theory.
• The interlace polynomial of a graph
• Vertex-minors, monadic second-order logic, and a conjecture by Seese
• Reducing prime graphs and recognizing circle graphs
• Representations of graphs and networks (coding, layouts and embeddings)
• Circle graph obstructions
• Monadic second-order definable graph transductions: a survey
• The monadic second-order logic of graphs. X: Linear orderings
• Efficient graph representations
• The monadic second-order logic of graphs. XII: Planar graphs and planar maps
• Container ship stowage problem complexity and connection to the coloring of circle graphs
• Euler circuits and DNA sequencing by hybridization
• The monadic second-order logic of graphs. VIII: Orientations
• The monadic second-order logic of graphs. XIV: Uniformly sparse graphs and edge set quantifica\-tions.
• Algorithmic graph theory and perfect graphs
• Upper bounds to the clique width of graphs
• The monadic second-order logic of graphs. XV: On a conjecture by D. Seese
• Rank-width and vertex-minors
• Decomposition of Directed Graphs
• Recognition of Circle Graphs
• Handbook of Graph Grammars and Computing by Graph Transformation
• Recognizing circle graphs in polynomial time
• Generalized Quantifiers and Logical Reducibilities
• ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
• The monadic second-order logic of graphs XVI : Canonical graph decompositions
• On the Relationship Between Clique-Width and Treewidth
• Theory of Matroids
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Circle graphs and monadic second-order logic