论文标题
在最佳超越平面图上
On Optimal Beyond-Planar Graphs
论文作者
论文摘要
如果可以在平面中绘制具有特定限制的交叉点，则图形将超出平面。已经研究了几种类型的超越平面图，例如，如果每个边缘在最多的k次和RAC中都可以在直线图中以直角越过，则K-Planar如果每个边缘在大多数k时和RAC中都进行了。如果边数与其类型的密度重合，则图是最佳的。最佳图是特殊的，仅适用于某些类型的超越平面图，包括1平面，2平面和RAC图。对于已知最佳图的所有类型的超越平面图，我们计算最佳图形的范围，建立组合属性，并显示每个图都是最佳图的拓扑小调。请注意，次要属性是众所周知的一般平面图。
A graph is beyond-planar if it can be drawn in the plane with a specific restriction on crossings. Several types of beyond-planar graphs have been investigated, such as k-planar if every edge is crossed at most k times and RAC if edges can cross only at a right angle in a straight-line drawing. A graph is optimal if the number of edges coincides with the density for its type. Optimal graphs are special and are known only for some types of beyond-planar graphs, including 1-planar, 2-planar, and RAC graphs. For all types of beyond-planar graphs for which optimal graphs are known, we compute the range for optimal graphs, establish combinatorial properties, and show that every graph is a topological minor of an optimal graph. Note that the minor property is well-known for general beyond-planar graphs.
