Algorithms in computational geometry and graph drawing

点击翻译按钮获取中文摘要

My research is in design and analysis of algorithms -- specifically in the areas of computational geometry and graph algorithms. ******Graph representations are ubiquitous in computer science, engineering and the sciences -- a few examples are: road/electical/internet networks in engineering, molecular structures in chemistry, and evolutionary trees in biology. Geometry, sometimes intrinsic, and sometimes imposed, is often a valuable part of a graph representation. A big part of my work is about devising algorithms to find, manipulate and utilize such geometric representations of graphs. Specifically, one of the topics I propose working on is algorithms to represent two graphs that share some vertices and edges, with the constraint that the shared part be represented consistently. ******A current active research area is the study of algorithms to "reconfigure" geometric or combinatorial structures. "Morphing" is a popular term for some special cases of reconfiguration. I propose working on algorithms to morph between two representations of the same graph while preserving some geometric structure such as planarity. I also propose working on reconfiguration of triangulations via discrete moves called "flips". ******In a more geometric vein, my work on reconfiguration focuses on folding and flattening polyhedra. These problems have applications in manufacturing 3D shapes out of metal, cardboard or plastic. One problem is to flatten the surface of a polyhedron (e.g. imagine flattening a paper bag) continuously without using too many creases. When the surface is not flexible, Cauchy's rigidity theorem limits what can be done; we are investigating how much of the surface must be cut or made flexible to permit flattening.**