On the bandwidth of triangulated triangles (Q1842168): Difference between revisions

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\).