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.