Radial Level Planarity Testing and Embedding in Linear Time
Radial Level Planarity Testing and Embedding in Linear Time
复制标题
线性时间内的径向平面度测试和嵌入
DOI：
10.1007/978-3-540-24595-7_37
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
Michael Forster
中科院分区：
文献类型：
--
作者：
C. Bachmaier;F. Brandenburg;Michael Forster
每一个平面图都基于广度优先搜索有一种同心表示，见[21]。顶点被放置在同心圆圈上，边被绘制成无交叉的曲线。这里我们采取相反的观点。如果一个图的顶点在给定划分下被分到k个同心圆圈上，并且边能够在圆圈之间无交叉地单调绘制，那么这个图是k - 径向平面的。径向平面性是层平面性的一种推广，在层平面性中顶点被放置在k条水平线上。我们扩展了[18, 17, 15, 16, 12, 13]中层平面性测试的技术，并表明径向平面性在线性时间内是可判定的，并且一个径向平面嵌入能够在线性时间内被计算出来。
Every planar graph has a concentric representation based on a breadth first search, see [21]. The vertices are placed on concentric circles and the edges are routed as curves without crossings. Here we take the opposite view. A graph with a given partitioning of its vertices onto k concentric circles is k-radial planar, if the edges can be routed monotonic between the circles without crossings. Radial planarity is a generalisation of level planarity, where the vertices are placed on k horizontal lines. We extend the technique for level planarity testing of [18,17,15,16,12,13] and show that radial planarity is decidable in linear time, and that a radial planar embedding can be computed in linear time.