论文标题
粉丝交叉的免费图形及其与其他平面图的关系
Fan-Crossing Free Graphs and Their Relationship to other Beyond-Planar Graphs
论文作者
论文摘要
如果图形在平面上有图形，则图形为\ emph {fan-crossing free}，以便每个边缘都被独立边缘交叉，即交叉边缘具有不同的顶点。另一方面，如果交叉边缘具有一个共同的顶点，那就是\ emph {fan-crossing}，即它们形成风扇。两者都是超越平面图的突出例子。 $ k $ - 平面，$ k $ -gap-planar，quasi-planar和正确的角度交叉图。我们使用细分，节点到圆的扩展和路径添加操作来区分所有这些图形类。特别是，我们表明，任何图形的2个补充和节点到圆形的扩展都是免费的，这不适合粉丝交叉，$ k $ - （gap） - 平面图。因此，我们获得了免费的粉丝划线的图形，既不是粉丝交叉，也不是$ k $ - （gap） - 平面。最后，我们表明有些图具有独特的粉丝横断性嵌入，并且最大粉丝跨的图形较薄，并且对于粉丝跨的免费图形的识别问题是NP完整的。
A graph is \emph{fan-crossing free} if it has a drawing in the plane so that each edge is crossed by independent edges, that is the crossing edges have distinct vertices. On the other hand, it is \emph{fan-crossing} if the crossing edges have a common vertex, that is they form a fan. Both are prominent examples for beyond-planar graphs. Further well-known beyond-planar classes are the $k$-planar, $k$-gap-planar, quasi-planar, and right angle crossing graphs. We use the subdivision, node-to-circle expansion and path-addition operations to distinguish all these graph classes. In particular, we show that the 2-subdivision and the node-to-circle expansion of any graph is fan-crossing free, which does not hold for fan-crossing and $k$-(gap)-planar graphs, respectively. Thereby, we obtain graphs that are fan-crossing free and neither fan-crossing nor $k$-(gap)-planar. Finally, we show that some graphs have a unique fan-crossing free embedding, that there are thinned maximal fan-crossing free graphs, and that the recognition problem for fan-crossing free graphs is NP-complete.
