Approximation algorithms for Graph Drawing

图形绘制的近似算法

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

In applications such as social networks, street maps, entity-relationship diagrams for data bases, organizational hierarchies and control flow diagrams for software engineering, the underlying structure can be described abstractly as a graph: it consists of vertices (humans, sites, entities, employees, functions) and edges (relationships, streets, function calls) between them. Visualizing such graphs helps in analyzing their structure, for example for detecting clusters or similarities.  This motivates the problem of graph drawing: develop algorithms that automatically convert a graph into a picture that is easy to read.******User studies have shown that the most important criteria for legibility of a graph drawing is to minimize the number of crossings. Hence an important sub-area of graph drawing is how to draw a planar graph, i.e., a graph that could be drawn without any crossings at all. Many algorithms for drawing planar graphs exist, but although they are provably good with regard to some quality measure, they often give pictures that are far from best-possible for a given graph.******The topic of the proposed research is approximation algorithms for planar graph drawing, i.e., to develop algorithms with performance guarantees that are provably within a factor of the optimum for all graphs. Currently very few approximation algorithms for drawing planar graphs exist. Even the key ingredients for using well-known techniques for approximation algorithms (such as LP relaxation and Baker's technique) have rarely been studied.  I recently made progress on these key ingredients for the objective of minimizing the area, and plan to expand the work into developing approximation algorithms for minimum-area drawings  A major challenge for this is to develop new lower bound tools for planar graph drawing, since the existing lower-bound tools have proved insufficient for approximation algorithms.  Possibly no approximation algorithms exist, and so another avenue of my proposed research is to prove such impossibilites by applying the techniques of APX-hardness from complexity theory.  ***In the longer term, many other graph drawing objectives are used in the applications, and developing approximation algorithms for them is an exciting challenge. Such algorithms would give graph drawings that are provably not too far from the best-possible drawing of the given input graph, and hence should be a significant improvement for displaying the graph-structures of the above application areas.**

在社交网络、街道地图、数据库实体关系图、软件工程的组织层次结构和控制流程图等应用中，底层结构可以抽象地描述为图：它由顶点（人、站点、实体、员工、函数）以及它们之间的边（关系、街道、函数调用）有助于分析它们的结构，例如检测集群或相似性，这激发了图形绘制的问题：开发该算法。自动将图表转换为易于阅读的图片。*****用户研究表明，图表绘制的易读性最重要的标准是尽量减少交叉数量，因此是一个重要的子区域。图形绘制是如何绘制平面图，即可以在没有任何交叉的情况下绘制的图形，存在许多绘制平面图的算法，但尽管它们在某些质量度量方面被证明是好的，但它们通常给出的图片是这样的。远非最佳可能所提出的研究主题是平面图绘制的近似算法，即开发具有可证明在所有图的最优因子内的性能保证的算法，目前很少有近似算法。即使是使用众所周知的近似算法技术（例如 LP 松弛和 Baker 技术）的关键要素，我最近也很少研究这些关键要素以最小化目标。面积，并计划将工作扩展到开发最小面积绘图的近似算法。这方面的一个主要挑战是开发用于平面图绘制的新下限工具，因为现有的下限工具已被证明不足以用于近似算法。近似算法是存在的，因此我提出的研究的另一个途径是通过应用复杂性理论中的 APX 硬度技术来证明这种不可能。***从长远来看，许多其他图。应用程序中使用绘图目标，为它们开发近似算法是一项令人兴奋的挑战，此类算法所提供的图形绘图可证明与给定输入图的最佳可能绘图相差不远，因此应该是一个重大改进。用于显示上述应用领域的图形结构。**