Linear layouts measuring neighbourhoods in graphs

DOI10.1016/j.disc.2006.03.048zbMath1103.68093OpenAlexW2006729834MaRDI QIDQ2502893

Frank Gurski

Publication date: 13 September 2006

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

Full work available at URL: https://doi.org/10.1016/j.disc.2006.03.048

zbMATH Keywords

cut-widthgraph layout parameter neighbourhood-width

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (13)

Clique-width of path powers ⋮ Graphs of Linear Clique-Width at Most 3 ⋮ Characterising the linear clique-width of a class of graphs by forbidden induced subgraphs ⋮ Clique-width with an inactive label ⋮ Classes of graphs with low complexity: the case of classes with bounded linear rankwidth ⋮ Graph parameters measuring neighbourhoods in graphs-bounds and applications ⋮ Computing the Clique-Width of Large Path Powers in Linear Time via a New Characterisation of Clique-Width ⋮ Neighbourhood-width of trees ⋮ Characterizations of monadic NIP ⋮ Graphs of linear clique-width at most 3 ⋮ Comparing linear width parameters for directed graphs ⋮ Linear rank-width and linear clique-width of trees ⋮ A characterisation of clique-width through nested partitions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Monadic second-order evaluations on tree-decomposable graphs
• Characterizations for co-graphs defined by restricted NLC-width or clique-width operations
• Graph minors. I. Excluding a forest
• Graphs with small bandwidth and cutwidth
• The vertex separation number of a graph equals its path-width
• A partial k-arboretum of graphs with bounded treewidth
• \(k\)-NLC graphs and polynomial algorithms
• The monadic second-order logic of graphs. XIV: Uniformly sparse graphs and edge set quantifica\-tions.
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• Approximating clique-width and branch-width
• On the relationship between NLC-width and linear NLC-width
• Complexity of Finding Embeddings in a k-Tree
• Graph Classes: A Survey
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Deciding Clique-Width for Graphs of Bounded Tree-Width
• The Pathwidth and Treewidth of Cographs
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Linear layouts measuring neighbourhoods in graphs