The 'bisection width' of a graph is defined as the minumum number of edges that need to be removed to partition the graph into two equal halves. If the graph is 'sparse', then we don't expect this quantity to be large.

This talk will provide a brief introduction to the art gallery problem, which was first posed to Chvátal by Victor Klee in 1973.

This will be a talk on the proof of NP hardness of the Art Gallery Problem (which was described by Pritam last week). Approximation algorithms for the terrain guarding problem will also be described.