Visibility Representations with 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.