Algorithms for near-planar graphs

地铁地图、实体关系图、社会网络、街道地图、层级组织、控制流程图和生化途径有什么共同之处？它们都是可以建模为图的结构和关系的例子：由顶点（表示站点，节点，点，.. . .）和边缘，即，顶点对（表示连接、弧、街道、含义，. . . ).通常，人们想知道这些结构的一些特性（“无线电站点需要多少不同的频率来避免干扰？“，“多少人都互相认识？“，“从A到B最近的路是什么？“），当这些问题转化为图的语言时，就成为著名的着色、团和最短路等优化问题。图的一个常用的研究子类是平面图，它可以在平面上画出而没有交叉。它们经常出现在应用程序中：例如，表示几何站点之间相互作用的图（如Delauney三角剖分）通常是平面的。平面图中的优化问题已经被深入研究了几十年，并且已知许多例子，其中平面图中的优化问题可以比任意图中的优化问题更有效地解决。也有一些通用的工具来开发平面图的算法，如贝克近似方案，分离器和二维性。在真实的生活中，由诸如道路网络之类的应用产生的图通常接近于平面，但确实需要一些交叉点（例如，地下通道与桥梁相遇的地方）。近年来，这引起了人们对所谓的“近平面图”的极大兴趣-这是一个包罗万象的术语，指任何一类不一定是平面的，但在某种程度上是“接近”的图。这些的主要例子是小亏格的图（即，它们可以嵌入到小亏格的表面中），k平面图（即，每条边最多可具有K个交叉）或几何图的一般化（例如，高阶Delauney三角测量）。所提出的研究的目标是找到更好的算法，这样的近平面图的优化问题。对于小亏格的图（一般来说，所有所谓的H-小自由图）已经有相当多的了解。然而，对于其他近平面图，大多数现有的结果要么集中在性质（“有多少条边？“）或通过平面化图形而简单地获得。很少有算法是已知的优化问题，我建议探索这样的算法，短期目标是将众多已知的平面图的结果，近平面图，和建立通用工具的长期愿景开发算法近平面图。这个主题非常适合HQP培训，使他们能够发展逻辑思维和解决问题的技能，这对他们以后在软件行业或学术界的工作至关重要。

What do a subway map, an entity-relationship diagram, a social network, a street map, a hierarchical organization, a control flow diagram and a biochemical pathway have in common? They are all examples of structures and relationships that can be modeled as a graph: an abstract structure consisting of vertices (representing sites, nodes, points, . . . ) and edges, i.e., pairs of vertices (representing connections, arcs, streets, implications, . . . ). Typically one wants to know some properties of these structures ("how many different frequencies do radio sites need to avoid interference?", "how many people all mutually know each other?", "what is the shortest way to get from A to B?") which, when translated to the language of graphs, become the well-known optimization problems of coloring, clique and shortest path. One commonly studied subclass of graphs are the planar graphs, which can be drawn in the plane without crossings. They frequently appear in applications: for example graphs (such as Delauney triangulations) that express interactions between geometric sites are often planar. Optimization-problems in planar graphs have been studied intensely for many decades, and many examples are known where optimization problems can be solved more efficiently in planar graphs than in arbitrary graphs. There also exist some general-purpose tools for developing algorithms for planar graphs, such as Baker's approximation scheme, separators and bidimensionality. In real life, graphs arising from applications such as road networks are often close to planar, but do require a few crossings (e.g. where an underpass meets a bridge). In recent years, this has caused much interest in so-called "near-planar graphs"---a catch-all term for any class of graphs that are not necessarily planar, but that are "close" in some way. Prime examples of these are graphs of small genus (i.e., they can be embedded in a surface of small genus), k-planar graphs (i.e., every edge can have at most k crossings) or generalization of geometric graphs (e.g., higher-order Delauney triangulation). The goal of the proposed research is to find better algorithms for optimization problems for such near-planar graphs. Quite a bit is known already for graphs of small genus (and generally, all so-called H-minor free graphs). However, for other near-planar graphs most existing results either focus on properties ("how many edges are there?") or are trivially obtained by planarizing the graph. Few algorithms are known for optimization problems; I propose to explore such algorithms, with the short-term objective of transferring numerous known results for planar graphs to near-planar graphs, and the long-term vision of establishing general-purpose tools for developing algorithms for near-planar graphs. This topic is ideally suited for HQP training, enabling them to develop the logical thinking and problem-solving skills crucial for their later work in the software industry or academia.