Algorithms in computational geometry and graph drawing

我的研究方向是算法的设计和分析，特别是计算几何和图形算法。 * * 图形表示在计算机科学，工程和科学中无处不在-一些例子是：工程中的道路/电子/互联网网络，化学中的分子结构，以及生物学中的进化树。 几何，有时是内在的，有时是强加的，通常是图形表示的有价值的部分。 我工作的很大一部分是关于设计算法来寻找、操作和利用这种图形的几何表示。 具体地说，我建议研究的主题之一是表示两个共享一些顶点和边的图的算法，其中的约束是共享部分被一致地表示。 * * 当前活跃的研究领域是研究"重新配置"几何或组合结构的算法。"变形"是一个流行的术语，用于描述一些特殊的重新配置情况。我建议研究在同一个图的两个表示之间变形的算法，同时保留一些几何结构，如平面性。 我还建议通过离散移动（称为“翻转”）重新配置三角测量。 * * 在一个更几何的静脉，我的工作重新配置的重点是折叠和展平多面体。 这些问题在用金属、纸板或塑料制造3D形状中有应用。 一个问题是在不使用太多折痕的情况下连续地压平多面体的表面（例如，想象压平纸袋）。 当曲面不是柔性的时，柯西刚性定理限制了所能做的事情;我们正在研究曲面的多少必须被切割或使其柔性化以允许展平。

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.**