Properties of beyond-planar graphs

点击翻译按钮获取中文摘要

A topological graphs is a graph drawn in the plane. Such graphs are distinguished by the types of edge crossings. The planar graphs, the best known graph class, excludes edge crossings. Classes of graphs with restrictions on crossings are called beyond-planar graphs. Examples are k-planar graphs, where each edge is crossed at most k times, fan-crossing graphs, where the crossing edges are incident to a common endpoint or fan-crossing free graphs, where such crossings are excluded. Empirical studies have shown a strong correlation between the type and the number of edge crossings and the readability of a graph drawing. We study structural properties of classes of beyond-planar graphs, and distinguish different beyond-planar graph classes by new operations on graphs.