On the Recognition of Fan-Planar and Maximal Outer-Fan-Planar Graphs
On the Recognition of Fan-Planar and Maximal Outer-Fan-Planar Graphs
复制标题
论扇形平面和最大外扇形平面图的识别
作者：
M. Bekos;Sabine Cornelsen;L. Grilli;Seok;M. Kaufmann
扇形平面图是最近提出的1-平面图的推广。图是扇面的，如果它可以嵌入到平面中，使得每条被多次相交的边都被与一个公共顶点关联的两条或更多条边的丛相交。一个图是外扇平面的，如果它有一个扇面嵌入，其中每个顶点都在外面上。另外，如果边的插入破坏了它的外扇平面性，则它是最大外扇平面。本文给出了一个线性时间算法来判定一个给定的图是否为极大外扇平面。如果存在外部扇面嵌入，则该算法也可用于产生外部扇面嵌入。反之，我们证明了在给定旋转系统(即每个顶点周围的边的循环顺序)的情况下，测试图的扇平面性是NP完全的。
Fan-planar graphs were recently introduced as a generalization of 1-planar graphs. A graph is fan-planar if it can be embedded in the plane, such that each edge that is crossed more than once, is crossed by a bundle of two or more edges incident to a common vertex. A graph is outer-fan-planar if it has a fan-planar embedding in which every vertex is on the outer face. If, in addition, the insertion of an edge destroys its outer-fan-planarity, then it is maximal outer-fan-planar. In this paper, we present a linear-time algorithm to test whether a given graph is maximal outer-fan-planar. The algorithm can also be employed to produce an outer-fan-planar embedding, if one exists. On the negative side, we show that testing fan-planarity of a graph is NP-complete, for the case where the rotation system (i.e., the cyclic order of the edges around each vertex) is given.
关于扇形交叉自由图的边数
影响因子：
1.1
作者：
Otfried Cheong;Sariel Har-Peled;Heuna Kim;Hyo-Sil Kim
通讯作者：
Hyo-Sil Kim