The monadic second-order logic of graphs. XII: Planar graphs and planar maps

DOI10.1016/S0304-3975(99)00305-9MaRDI QIDQ1566702zbMATH OpenFDO

Authors Bruno Courcelle

Publication date 4 June 2000

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0304-3975(99)00305-9

zbMATH Keywords

monadic second-order logicplanar graphgraph drawingdepth-first search treeordered structure3-connected graphrotation systemextension of first-order logic

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph theory (05C99)

Recommendations

• Graph equivalences and decompositions definable in monadic second-order logic. The case of circle graphs
• Map genus, forbidden maps, and monadic second-order logic
• scientific article; zbMATH DE number 1059243
• The monadic second order logic of graphs. VI: On several representations of graphs by relational structures
• The monadic second-order logic of graphs. IV: Definability properties of equational graphs

Cites work

• scientific article; zbMATH DE number 3882430 (Why is no real title available?)
• scientific article; zbMATH DE number 4006288 (Why is no real title available?)
• scientific article; zbMATH DE number 1262783 (Why is no real title available?)
• scientific article; zbMATH DE number 1025912 (Why is no real title available?)
• scientific article; zbMATH DE number 1059243 (Why is no real title available?)
• scientific article; zbMATH DE number 803291 (Why is no real title available?)
• scientific article; zbMATH DE number 1392292 (Why is no real title available?)
• Easy problems for tree-decomposable graphs
• Graphs on surfaces
• Monadic second-order definable graph transductions: a survey
• Monadic second-order evaluations on tree-decomposable graphs
• The monadic second order logic of graphs. VI: On several representations of graphs by relational structures
• The monadic second-order logic of graphs. VIII: Orientations
• The monadic second-order logic of graphs. X: Linear orderings
• The monadic second-order logic of graphs. XI: Hierarchical decompositions of connected graphs
• The monadic second-order logic of graphs. XIII: Graph drawings with edge crossings

Cited in

(13)

• Trees, grids, and MSO decidability: from graphs to matroids
• Map genus, forbidden maps, and monadic second-order logic
• Affine optimal k-proper connected edge colorings
• GETGRATS: a summary of scientific results (with annotated bibliography)
• The common structure of the curves having a same Gauss word
• Circle graphs and monadic second-order logic
• Counting on rainbow k-connections
• Computing crossing numbers in quadratic time
• On zero-one and convergence laws for graphs embeddable on a fixed surface
• A monadic second-order definition of the structure of convex hypergraphs.
• The monadic second-order logic of graphs. XIII: Graph drawings with edge crossings
• Specification and verification of a linear-time temporal logic for graph transformation
• Definability equals recognizability for \(k\)-outerplanar graphs and \(l\)-chordal partial \(k\)-trees

This page was built for publication: The monadic second-order logic of graphs. XII: Planar graphs and planar maps

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1566702)