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

DOI10.1016/J.DAM.2018.07.022MaRDI QIDQ2174559zbMATH OpenOpenAlexWikidataFDO

Authors 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

bounded expansion graph classclique-widthmonadic second-order logicquasi-planar graphtree-width

Mathematics Subject Classification ID

Higher-order logic (03B16) 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)

Recommendations

• Quasi-planar graphs have a linear number of edges
• Parameterized complexity of 1-planarity
• New graph classes of bounded clique-width
• The effect of planarization on width
• scientific article; zbMATH DE number 1953082

Cites work

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

Cited in

(3)

• Grammars and clique-width bounds from split decompositions
• On Planar Quasi-Parity Graphs
• On using SAT solvers for graph computations

Describes a project that uses

Uses Software

• ComputeTW

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

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