Graph parameters measuring neighbourhoods in graphs-bounds and applications

DOI10.1016/j.dam.2007.09.004zbMath1200.05144OpenAlexW1974613721MaRDI QIDQ944739

Frank Gurski

Publication date: 10 September 2008

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

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

zbMATH Keywords

VLSIgraph drawinggraph layoutneighbourhood widthneighbourhoods in graphs

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

Comparing linear width parameters for directed graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An algorithm for finding homogeneous pairs
• On minimizing width in linear layouts
• Bull-free Berge graphs are perfect
• Parallel concepts in graph theory
• Linear layouts measuring neighbourhoods in graphs
• On the relationship between NLC-width and linear NLC-width
• On Bipartite Drawings and the Linear Arrangement Problem
• Clique-width minimization is NP-hard
• Upper and Lower Bounds on the Complexity of the Min-Cut Linear Arrangement Problem on Trees
• A Randomized Fully Polynomial Time Approximation Scheme for the All-Terminal Network Reliability Problem
• Cutwidth of the de Bruijn graph
• ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
• Graph-Theoretic Concepts in Computer Science
• A polyhedral approach to planar augmentation and related problems