Computing the Stretch of an Embedded Graph
Computing the Stretch of an Embedded Graph
复制标题
计算嵌入图的拉伸
DOI：
10.1137/130945636
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Hlineny P.
中科院分区：
文献类型：
--
作者：
Cabello S;Chimani M;Hlineny P.
设是一个嵌入可定向曲面中的图，可能具有边权，用圈的长度（边数或边权之和）表示。嵌入曲面上的图的拉伸是所有圈对中恰好交叉一次的最小值。我们提供了两种算法来计算嵌入图的拉伸，每种算法都基于不同的原理。第一种算法基于外科手术，以高概率在时间上计算拉伸，或者在最坏情况下在时间上计算拉伸，其中是曲面的亏格，是中的顶点数。第二种算法基于使用短同调基并计算时间上的拉伸。
Letbe a graph embedded in an orientable surface, possibly with edge weights, and denote bythe length (the number of edges or the sum of the edge weights) of a cyclein. The stretch of a graph embedded on a surface is the minimum ofover all pairs of cyclesandthat cross exactly once. We provide two algorithms to compute the stretch of an embedded graph, each based on a different principle. The first algorithm is based on surgery and computes the stretch in timewith high probability, or in timein the worst case, whereis the genus of the surfaceandis the number of vertices in. The second algorithm is based on using a short homology basis and computes the stretch in time.
DOI：
10.1137/120872310
发表时间：
2012-03
期刊：
ArXiv
影响因子：
--
作者：
Sergio Cabello;B. Mohar
通讯作者：
Sergio Cabello;B. Mohar
影响因子：
0.8
作者：
H. Djidjev;I. Vrto
通讯作者：
I. Vrto
在平面图中添加一条边会使交叉数变得困难
DOI：
10.1145/1810959.1810972
发表时间：
2010
期刊：
Proceedings of the twenty-sixth annual symposium on Computational geometry
影响因子：
--
作者：
Sergio Cabello;B. Mohar
通讯作者：
B. Mohar