Center and diameter problems in plane triangulations and quadrangulations
Center and diameter problems in plane triangulations and quadrangulations
复制标题
平面三角剖分和四边形剖分中的中心和直径问题
DOI：
--
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
Y. Vaxès
中科院分区：
文献类型：
--
作者：
V. Chepoi;F. Dragan;Y. Vaxès
在本文中，我们提出了第一个线性时间算法，用于计算几类面正平面图的中心和直径：内部顶点次数≥6的三角剖分、内部顶点次数≥4的四边形以及由该网格的简单电路界定的正六边形网格的子图。
In this note, we present first linear time algorithms for computing the center and the diameter of several classes of face regular plane graphs: triangulations with inner vertices of degree ≥ 6, quadrangulations with inner vertices of degree ≥ 4 and the subgraphs of the regular hexagonal grid bounded by a simple circuit of this grid.