Visibility Representations with Crossings

具有交叉口的可见性表示

• 批准号: 239775286
• 负责人: Professor Dr. Franz Josef Brandenburg
• 金额: --
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2013
• 资助国家: 德国
• 起止时间: 2012-12-31 至 2015-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/239775286?language=en
• 关键词: Visibility; Representations; Crossings

Graphs are an important tool for modelling discrete structures. They are also known as networks, plans, diagrams or schemas. The wide use of graphs is based on the fact that there is a drawing.The planar graphs are the best known and mostly investigated class of graphs. However, most graphs are non-planar, particularly in applications. This has recently lead to the introduction of beyond-planar graphs. Such graphs have crossings in some regulated way, and they adopt important properties from planar graphs, such as as a linear number of edges and drawing algorithms. Planar graphs are commonly drawn straight line. There are orthogonal drawings with horizontal and vertical line segments and visibility representations, where vertices are represented by horizontal lines and edges by a vertical visibility between the respective vertices. Visibility representations are less common than straight-line drawings, but they are algorithmically easier and conceptually more flexible. There is an unexplored potentential behind visibility representations if crossings are allowed in some controlled way. Then visibility representations dominate convential drawing styles. They provide many options to define beyond-planar graphs. In this project we wish to explore this potential of visibility representations. In particular, we define new classes of beyond-planar graphs and shall investigate typical graph theoretic properties and the complexity of recognition problems. Moreover, we shall develop optimized graph drawing algorithms. Our studies shall help to develop beyond-planarity.

图是离散结构建模的重要工具。它们也被称为网络，计划，图表或模式。图的广泛应用是基于有图这一事实，平面图是最著名和研究最多的一类图。然而，大多数图是非平面的，特别是在应用中。最近，这导致了超平面图的引入。这类图以某种规则的方式有交叉，并且它们采用了平面图的重要性质，例如线性边数和绘制算法。平面图通常是画直线的。存在具有水平和垂直线段以及可见性表示的正交绘图，其中顶点由水平线表示，边缘由相应顶点之间的垂直可见性表示。可见性表示不如直线图形常见，但它们在算法上更简单，在概念上更灵活。如果以某种受控的方式允许交叉，那么可见性表示背后还有未开发的潜力。可见性表示在传统的绘图风格中占主导地位。它们提供了许多定义超平面图的选项。在这个项目中，我们希望探索这种潜在的可见性表示。特别是，我们定义了新的类超越平面图，并将调查典型的图论性质和识别问题的复杂性。此外，我们将开发优化的图形绘制算法。我们的研究将有助于超平面性的发展。

项目成果

Recognizing Optimal 1-Planar Graphs in Linear Time

识别线性时间内的最优一平面图

• DOI: 10.1007/s00453-016-0226-8
• 期刊: Algorithmica
• 影响因子: 1.1
• 作者: F. J. Brandenburg

Recognizing and drawing IC-planar graphs

• DOI: 10.1016/j.tcs.2016.04.026
• 发表时间: 2015-09
• 期刊: Deep-sea Research Part Ii-topical Studies in Oceanography
• 影响因子: 3
• 作者: F. Brandenburg;W. Didimo;W. Evans;Philipp Kindermann;G. Liotta;Fabrizio Montecchiani

Outer 1-Planar Graphs

• DOI: 10.1007/s00453-015-0002-1
• 发表时间: 2016-04
• 期刊: Algorithmica
• 影响因子: 1.1
• 作者: Christopher Auer;C. Bachmaier;F. Brandenburg;Andreas Gleißner;Kathrin Hanauer;Daniel Neuwirth;Josef Reislhuber