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.