Applied graph algorithms

算法图论在实践和其他研究领域都有广泛的应用。在这个项目中，我建议处理一些主要在计算几何、形式语言和分布式计算领域出现的图论算法问题。图的绘制是一个重要的领域，除了计算几何外，还涉及到知识表示、图论、人类认知和许多其他领域。这里的基本问题是如何可视化表示结构知识的图形，以便人类在面对这种可视化时能够轻松地感知到它的一些重要属性，例如为了快速做出关键决策。我想设计一些图形类的绘图算法。多边形物体在平面上的运动可以用几何图形来表示。在机器人、运动规划和抓取方面，研究了它们在平面环境中不受障碍物干扰的机动性。为了固定一个多边形对象,一动不动的障碍被放置在其边界,防止刚性运动。我提出用一组点来研究多边形物体的最优固定，根据不同的最优性准则。数据包分类的一种方法是使用有限状态自动机。自动机读取输入字符串，并在与此分类结果相对应的最终状态停止。关于这类自动机的几个问题转化为与某些图类有关的图论问题。在我的研究中，我将研究这类图的一些算法，这在实践中很重要，因为我的项目的这一部分直接来自于一个工业应用。分布式计算中的几个问题涉及到使用一组协作的移动代理沿着图行走的图调查。我打算针对某些类别的图研究移动代理的图调查模型。

Algorithmic graph theory has numerous applications either directly in practice or in other research fields. In this project I propose to deal with some graph theory algorithmic problems arising mainly in the fields of computational geometry, formal languages and distributed computing.         Graph drawing is an important domain, related, besides computational geometry, to the fields of knowledge representation, graph theory, human cognition and many others. The fundamental question here is how to visualize a graph representing structural knowledge, so that a human confronted with this visualization will easily perceive some of its important properties, for example in order to make critical decisions fast. I would like to design the drawing algorithms for some classes of graphs.         A motion of polygonal objects in the plane may be represented by geometric graphs. Their mobility within the plane environment, without interfering with obstacles, was studied in robotics, motion planning and grasping. In order to immobilize a polygonal object, motionless obstacles are placed around its boundary, preventing any rigid movement. I propose to study optimal immobilizations of polygonal objects with a set of points, according to different criteria of optimality.         One of the approaches to data packet classification uses finite state automata. An automaton reads an input string and stops in the final state corresponding to the result of this classification. Several problems concerning such automata transform to graph-theoretical questions related to some classes of graphs. In my research, I will study some algorithms for this class of graphs, important in practice, since this portion of my project comes directly from an industrial application.         Several problems in distributed computing relate to graph investigation by use of sets of collaborating mobile agents, walking along the graph. I intend to study models of graph investigation by mobile agents for some classes of graphs.