Untangling Polygons and Graphs
Untangling Polygons and Graphs
复制标题
理清多边形和图形
DOI：
10.1007/s00454-009-9150-x
复制
发表时间：
2008
影响因子：
0.8
通讯作者：
Josef Cibulka
中科院分区：
文献类型：
--
作者：
Josef Cibulka
解缠是将平面图中的一些顶点移动以获得直线平面图的过程。目标是移动尽可能少的顶点。我们提出了一种算法，可以在保持Ω（n2/3）个顶点固定的情况下解开循环图Cn。对于任何连通图G，我们还给出了最坏情况下固定顶点数量的上界。这个界是G的顶点数、最大度和直径的函数。一个结果是每个3-连通平面图都有一个图δ使得在δ的每一次解缠结中至多O（（nlogn）2/3）个顶点是固定的.
Untangling is a process in which some vertices in a drawing of a planar graph are moved to obtain a straight-line plane drawing. The aim is to move as few vertices as possible. We present an algorithm that untangles the cycle graphCnwhile keeping Ω(n2/3) vertices fixed.For any connected graphG, we also present an upper bound on the number of fixed vertices in the worst case. The bound is a function of the number of vertices, maximum degree, and diameter ofG. One consequence is that every 3-connected planar graph has a drawingδsuch that at mostO((nlogn)2/3) vertices are fixed in every untangling ofδ.
解开平面图。
DOI：
--
发表时间：
2009
期刊：
Discrete & Computational Geometry 42
影响因子：
--
作者：
Xavier Goaoc;Jan Kratochvil;Yoshio Okamoto;Chan-Su Shin;Andreas Spillner;Alexander Wolff
通讯作者：
Alexander Wolff