On the bandwidth of triangulated triangles

DOI10.1016/0012-365X(94)00208-ZMaRDI QIDQ1842168zbMATH OpenOpenAlexFDO

Authors Robert A. Hochberg, Colin McDiarmid, Michael Saks

Publication date 23 October 1995

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(94)00208-z

zbMATH Keywords

bandwidthplanar graphtriangulated triangles

Mathematics Subject Classification ID

Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Review text

The three authors give a technique for obtaining a lower bound on the bandwidth of any planar graph \(G\) by proving that if \(G\) is a plane near- triangulation and \(v_ 1\), \(v_ 2\), \(v_ 3\) are three mutually distinct vertices on the exterior face, the bandwidth of \(G\) is at least as large as the smallest connecting set with respect to \(v_ 1\), \(v_ 2\), \(v_ 3\).

Recommendations

• On the bandwidth of convex triangulation meshes
• Bounding the bandwidths for graphs
• Bandwidth of pyramidal meshes
• New bounds on the edge-bandwidth of triangular grids
• Edge-bandwidth of the triangular grid

Cites work

• Graph theory
• scientific article; zbMATH DE number 432834 (Why is no real title available?)
• scientific article; zbMATH DE number 4053698 (Why is no real title available?)
• Optimal labelling of a product of two paths
• Optimal numberings and isoperimetric problems on graphs

Cited in

(18)

• Edge-bandwidth of the triangular grid
• On the bandwidth of convex triangulation meshes
• Partitioning into graphs with only small components
• New results on edge-bandwidth
• 27 variants of Tutte's theorem for plane near-triangulations and an application to periodic spline surface fitting
• Topological properties on the diameters of the integer simplex
• Cyclic bandwidth with an edge added
• On the edge-bandwidth of graph products
• Lower bounds for the bandwidth problem
• Square-root rule of two-dimensional bandwidth problem
• Deciding Relaxed Two-Colourability: A Hardness Jump
• Cutwidth of triangular grids
• Bandwidth edge counts for linear arrangements of rectangular grids
• Enumerating Hamiltonian cycles
• New bounds on the edge-bandwidth of triangular grids
• Bandwidth and pathwidth of three-dimensional grids
• Bandwidth of pyramidal meshes
• Topologizing Sperner's lemma

This page was built for publication: On the bandwidth of triangulated triangles

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