<p><a href="http://www.cs.duke.edu/~bsayan/">Sayan Bhattacharya</a><br />
Duke University<br />
Department of Computer Science<br />
N303, North Building<br />
304 Research Drive<br />
Durham, NC 27708<br />
United States of America</p>
<p>Pinaki Mazumder<br />
University of Michigan<br />
Department of Electrical Engineering<br />
and Computer Science<br />
2260 Howard Avenue<br />
Ann Arbor, MI 48109-2121<br />
United States of America</p>
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.
