CS Faculty Candidate Colloquium
Friday ***Special Time and Location*** February 13 10:45 - 11:50 AM Kelley 1007 Glencora Borradaile Ph.D. in CS from Brown University Post-Doc Fellow at University of Waterloo Designing Algorithms for Planar Graphs Graph algorithms abound: telecommunications networks can be designed by finding low-cost subgraphs connecting terminals and analyzed using maximum flows and minimum cuts; logistics in road maps may amount to shortest paths or travelling salesperson tours; image segmentations are graph cuts. In these examples, not only can we model the problem as a graph problem, but often as a planar graph problem. Can we exploit this planar structure to design better, faster, more accurate algorithms for such problems? Consider a two-dimensional drawing, or embedding, of a planar graph. We can use this embedding as a guide for scanning through the graph, building a solution to a problem as we go. Alternatively, we can decompose the graph into small pieces (also planar), solve an easier problem in each piece, and combine the pieces together to build a solution for the original graph. Both techniques are inspired by geometric counterparts. We use the former to efficiently solve network-flow problems (such as maximum flow), and the latter to approximate NP-hard problems (such as Steiner tree). While planar graphs do arise in applications, we may occasionally face a few non-planarities: for example, bridges and tunnels in road maps. We can often turn such nearly-planar graphs into planar graphs and then proceed using planar techniques. This talk will highlight these techniques, illustrating how they have led to faster algorithms than currently achievable without using planarity and more accurate algorithms than possible (unless P=NP) for general graphs. Biography Glencora Borradaile received her Ph.D. in Computer Science from Brown University in 2008 and is now a postdoctoral fellow at the University of Waterloo. She completed an Honours Bachelor of Science degree in Applied Mathematics from the University of Western Ontario in 2002 and was awarded a Gold Medal as the top graduate of the program. Her research focusses on exploiting the structure of planar and almost-planar graphs to design more efficient or more accurate algorithms for combinatorial optimization problems. She has received two undergraduate research awards, two graduate scholarships and a postdoctoral fellowship from the Natural Science and Engineering Research Council of Canada. While at Brown University, she received a Kanellakis Graduate Fellowship, a Brown University Dissertation Fellowship and a Rowland Lloyd Graduate Award.
_______________________________________________ Colloquium mailing list [email protected] https://secure.engr.oregonstate.edu/mailman/listinfo/colloquium
