A Reduction System for Optimal 1-Planar Graphs
A Reduction System for Optimal 1-Planar Graphs
复制标题
最优一平面图的约简系统
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
F. Brandenburg
中科院分区：
文献类型：
--
作者：
F. Brandenburg
有一个图约简系统，使每个最佳的1-平面图可以减少到一个不可约的扩展轮图，提供的减少是这样应用的，以保持给定的图形类。一个图是最优1-平面的，如果它可以在平面上画出，每条边最多有一个交叉，如果它有最多4 n-8条边，则它是最优的。
我们表明，减少系统是上下文敏感的，以便保存的图形类可以授予本地条件，可以在恒定的时间进行测试。每一个最优1-平面图G都可以约简为每一个扩展轮图，其尺寸在从（次）最小尺寸到依赖于G的某个上界的范围内。如果G不是5-连通的，则存在最小扩张轮图的约化，反之则不然。约简系统具有副作用，并且是不确定的和非融合的。然而，减少量可以在线性时间内计算。
There is a graph reduction system so that every optimal 1-planar graph can be reduced to an irreducible extended wheel graph, provided the reductions are applied such that the given graph class is preserved. A graph is optimal 1-planar if it can be drawn in the plane with at most one crossing per edge and is optimal if it has the maximum of 4n-8 edges.
We show that the reduction system is context-sensitive so that the preservation of the graph class can be granted by local conditions which can be tested in constant time. Every optimal 1-planar graph G can be reduced to every extended wheel graph whose size is in a range from the (second) smallest one to some upper bound that depends on G. There is a reduction to the smallest extended wheel graph if G is not 5-connected, but not conversely. The reduction system has side effects and is non-deterministic and non-confluent. Nevertheless, reductions can be computed in linear time.
识别线性时间内的最优一平面图
影响因子：
1.1
作者：
F. J. Brandenburg
通讯作者：
F. J. Brandenburg