Bandwidth and pathwidth of three-dimensional grids

DOI10.1016/j.disc.2011.02.019zbMath1223.05142OpenAlexW2050587029MaRDI QIDQ534058

Yota Otachi, Ryohei Suda

Publication date: 10 May 2011

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

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

zbMATH Keywords

bandwidthpathwidthgridvertex isoperimetric problem

Mathematics Subject Classification ID

Paths and cycles (05C38) Connectivity (05C40)

Related Items

Catching an infinitely fast robber on a grid ⋮ Treewidth of Cartesian Products of Highly Connected Graphs ⋮ Structure of Graphs with Locally Restricted Crossings ⋮ Grid minors in damaged grids ⋮ Enumerating Hamiltonian cycles

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Compressions and isoperimetric inequalities
• Isoperimetric inequalities and fractional set systems
• The treewidth and pathwidth of hypercubes
• Edge-bandwidth of grids and tori
• Recognizing Cartesian products in linear time
• Antibandwidth of three-dimensional meshes
• Security number of grid-like graphs
• Treewidth and logical definability of graph products
• On explicit formulas for bandwidth and antibandwidth of hypercubes
• Graph minors. I. Excluding a forest
• Optimal labelling of a product of two paths
• Cyclic cutwidths of the two-dimensional ordinary and cylindrical meshes
• Lower bounds on the pathwidth of some grid-like graphs
• On the edge-bandwidth of graph products
• A Simple Proof of the Karakhanyan–Riordan Theorem on the Even Discrete Torus
• The bandwidth problem for graphs and matrices—a survey
• Optimal Indexing of the Vertices of Graphs
• An Ordering on the Even Discrete Torus
• Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
• Optimal numberings and isoperimetric problems on graphs