Philip Klein has been awarded a $300,000 grant from the National Science Foundation. The funding will support Klein's research on algorithms for solving optimization problems on planar graphs - graphs that can be drawn on the plane with no crossings. Such graphs are necessary in image processing and road map logistics.

Possible uses for planar graphs research are illustrated by the following scenario - imagine a truck driver who must develop the shortest possible route to supply vending machines at numerous locations. This scenario is a version of the infamous Traveling Salesman Problem; and finding the shortest route that visits ...