On quasi-planar graphs: clique-width and logical description

DOI10.1016/j.dam.2018.07.022zbMath1437.05059OpenAlexW2890330165WikidataQ129234160 ScholiaQ129234160MaRDI QIDQ2174559

Bruno Courcelle

Publication date: 21 April 2020

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2018.07.022

zbMATH Keywords

monadic second-order logicclique-widthtree-widthquasi-planar graphbounded expansion graph class

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Higher-order logic (03B16)

Related Items (1)

Grammars and clique-width bounds from split decompositions

Uses Software

• ComputeTW

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Coloring \(K_{k}\)-free intersection graphs of geometric objects in the plane
• 1-planarity of complete multipartite graphs
• On the model-checking of monadic second-order formulas with edge set quantifications
• Sparsity. Graphs, structures, and algorithms
• A survey of the algorithmic aspects of modular decomposition
• The behavior of clique-width under graph operations and graph transformations
• Characterisations and examples of graph classes with bounded expansion
• Rank-width and tree-width of \(H\)-minor-free graphs
• New graph classes of bounded clique-width
• Classifying the clique-width of \(H\)-free bipartite graphs
• Treewidth computations. I: Upper bounds
• Recent developments on graphs of bounded clique-width
• On the maximum number of edges in topological graphs with no four pairwise crossing edges
• Graphs drawn with few crossings per edge
• A partial k-arboretum of graphs with bounded treewidth
• A successful concept for measuring non-planarity of graphs: The crossing number.
• The monadic second-order logic of graphs. XIII: Graph drawings with edge crossings
• Characterising bounded expansion by neighbourhood complexity
• On the relationship between \(k\)-planar and \(k\)-quasi-planar graphs
• Automata for the verification of monadic second-order graph properties
• Linear time solvable optimization problems on graphs of bounded clique-width
• An annotated bibliography on 1-planarity
• From tree-decompositions to clique-width terms
• Clique-width for 4-vertex forbidden subgraphs
• The monadic second-order logic of graphs. XV: On a conjecture by D. Seese
• Approximating clique-width and branch-width
• A $c^k n$ 5-Approximation Algorithm for Treewidth
• Parameterized Complexity of 1-Planarity
• A SAT Approach to Clique-Width
• Re-embeddings of Maximum 1-Planar Graphs
• Clique-Width is NP-Complete
• Complexity of Finding Embeddings in a k-Tree
• Deciding Clique-Width for Graphs of Bounded Tree-Width
• Approximating rank-width and clique-width quickly
• Neighborhood complexity and kernelization for nowhere dense classes of graphs
• The Number of Edges in $k$-Quasi-planar Graphs
• On the Relationship Between Clique-Width and Treewidth
• Bounding the Clique‐Width of H‐Free Chordal Graphs
• Adding One Edge to Planar Graphs Makes Crossing Number and 1-Planarity Hard
• A Combinatorial Classic — Sparse Graphs with High Chromatic Number
• Rank‐width is less than or equal to branch‐width
• Computations by fly-automata beyond monadic second-order logic

This page was built for publication: On quasi-planar graphs: clique-width and logical description