Properties of beyond-planar graphs

超平面图的性质

• 批准号: 433963685
• 负责人: Professor Dr. Franz Josef Brandenburg
• 金额: --
• 依托单位国家: 德国
• 项目类别: Research Grants
• 资助国家: 德国
• 项目状态: 未结题
• 来源: https://gepris.dfg.de/gepris/projekt/433963685?language=en
• 关键词: Properties; 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.

拓扑图是在平面上画出的图。这些图通过边交叉的类型来区分。平面图是最著名的图类，不含边交叉。具有交叉限制的图类称为超平面图。例子是k-平面图，其中每个边最多交叉k次，扇形交叉图，其中交叉边与公共端点相关联，或扇形交叉自由图，其中排除此类交叉。经验研究表明，边交叉点的类型和数量与图形的可读性之间存在很强的相关性。研究了超平面图类的结构性质，并通过对图的新操作来区分不同的超平面图类。