Fan-Planar Graphs: Combinatorial Properties and Complexity Results
Fan-Planar Graphs: Combinatorial Properties and Complexity Results
复制标题
扇形平面图：组合属性和复杂性结果
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
I. Tollis
中科院分区：
文献类型：
--
作者：
Carla Binucci;E. D. Giacomo;W. Didimo;Fabrizio Montecchiani;M. Patrignani;I. Tollis
在图形的扇形平面绘制中，一条边只能交叉具有共同端点的边。扇形平面图最近由Kaufmann和Ueckerdt引入，他们证明了每个n顶点的扇形平面图最多有5n-10条边，并且这个边界对于ni¾？20是紧的。从组合和算法的角度对其结果进行了推广。我们证明了扇形平面图约束版本密度的紧界，并研究了扇形平面度和k平面度之间的关系。同时，我们证明了在变量嵌入条件下扇平面性的测试是np完全的。
In a fan-planar drawing of a graph an edge can cross only edges with a common end-vertex. Fan-planar drawings have been recently introduced by Kaufmann and Ueckerdt, who proved that every n-vertex fan-planar drawing has at most 5n-10 edges, and that this bound is tight for ni¾?20. We extend their result from both the combinatorial and the algorithmic point of view. We prove tight bounds on the density of constrained versions of fan-planar drawings and study the relationship between fan-planarity and k-planarity. Also, we prove that testing fan-planarity in the variable embedding setting is NP-complete.
关于扇形交叉自由图的边数
影响因子：
1.1
作者：
Otfried Cheong;Sariel Har-Peled;Heuna Kim;Hyo-Sil Kim
通讯作者：
Hyo-Sil Kim