Brown CS News

Philip Klein Wins NSF Grant For Optimization In Planar Graphs And Beyond


    Brown CS community members continue to win noteworthy grants and awards. To read more articles click here.

    Klein’s recent project (“Fast and accurate optimization in planar graphs and beyond”) has won a grant in the expected amount of $1.2M from the National Science Foundation (NSF), shared with Professor Jeff G. Erickson of the University of Illinois at Urbana-Champaign. Klein’s research involves discovering and analyzing algorithms for optimization problems in graphs, problems such as traveling salesman, shortest paths, network design, clustering, graph decomposition, and facility location.

    The grant supports work aimed at discovering algorithms that are designed specifically for planar graphs---graphs that can be drawn on a plane so that no edges cross. When the input graph is required to be a planar graph, we can achieve faster running times and more accurate approximations than we know how to achieve in general.  Road maps are nearly planar, so planar-graph algorithms are applicable to problems in logistics and planning in road maps. Grids are planar, so some problems in image processing can be addressed using planar-graph algorithms.