Properties of beyond-planar graphs

拓扑图是在平面上画的图。这类图通过边交叉的类型来区分。平面图是最著名的图类，它不包括边交叉。对交叉有限制的一类图称为超平面图。例如k-平面图，其中每条边至多相交k次，扇形交叉图，其中交叉边关联到公共端点，或者扇形交叉自由图，其中这种交叉被排除。经验研究表明，边交叉的类型和数量与图形的可读性之间存在很强的相关性。我们研究了超平面图类的结构性质，并通过对图的新运算来区分不同的超平面图类。

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.