Algorithms for near-planar graphs

近平面图的算法

• 批准号: RGPIN-2020-03958
• 负责人: Biedl, Therese
• 金额: $ 2.99万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=716738
• 关键词: Algorithms; near; planar; graphs

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.

地铁地图、实体关系图、社交网络、街道地图、层次结构、控制流程图和生化路径有什么共同点？它们都是可以建模为模型的结构和关系的示例？图：由顶点（代表地点、节点、点……）和边组成的抽象结构，即顶点对（代表连接、弧、街道、含义……）通常，人们想知道这些结构的一些属性（“无线电站点需要多少个不同的频率以避免干扰？”，“有多少人相互认识？”，“从 A 到达的最短路线是什么？到 B？”），当翻译成图的语言时，就变成了著名的着色、派系和最短路径优化问题。 一个经常研究的图的子类是平面图，它可以在平面上绘制而无需交叉。它们经常出现在应用程序中：例如，表达几何位置之间相互作用的图（例如德劳尼三角剖分）通常是平面的。平面图已经被深入研究了几十年，并且已知许多例子可以在平面图中比在任意图中更有效地解决优化问题。还存在一些用于开发平面图算法的通用工具。图，例如贝克近似方案、分隔符和二维。 在现实生活中，道路网络等应用产生的图形通常接近平面，但确实需要一些交叉点（例如地下通道与桥梁的交汇处），近年来，这引起了人们对所谓“近交叉点”的极大兴趣。平面图”——任何一类图的统称，这些图不一定是平面的，但在某种程度上“接近”。这些图的主要例子是小属图（即，它们可以嵌入到表面小属）、k 平面图（即每条边最多可以有 k 个交叉点）或几何图的推广（例如，高阶德劳尼三角剖分）。 所提出的研究的目标是为此类近平面图的优化问题找到更好的算法，对于小属图（通常是所有所谓的 H 小自由图），已经有相当多的了解。其他近平面图大多数现有结果要么关注属性（“有多少条边？”），要么通过平面化图来简单地获得优化问题，我建议探索此类算法。术语目标将平面图的大量已知结果转移到近平面图，以及建立用于开发近平面图算法的通用工具的长期愿景本主题非常适合 HQP 培训，使他们能够发展逻辑思维。以及解决问题的能力对于他们以后在软件行业或学术界的工作至关重要。