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.