Untangling Polygons and Graphs |
| |
Authors: | Josef Cibulka |
| |
Institution: | 1. Department of Applied Mathematics, Charles University, Malostranské nám. 25, 118 00, Prague, Czech Republic
|
| |
Abstract: | 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 graph C
n
while keeping Ω(n
2/3) vertices fixed.
For any connected graph G, 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 of G. One consequence is that every 3-connected planar graph has a drawing δ such that at most O((nlog n)2/3) vertices are fixed in every untangling of δ. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|