Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(6)
Connected Graph
Graph Drawing
Line Drawings
Maximum Degree
Planar Graph
Upper Bound
Subscribe
Academic
Publications
Untangling Polygons and Graphs
Untangling Polygons and Graphs,10.1007/s004540099150x,Discrete & Computational Geometry,Josef Cibulka
Edit
Untangling Polygons and Graphs
(
Citations: 1
)
BibTex

RIS

RefWorks
Download
Josef Cibulka
Untangling is a process in which some vertices in a drawing of a
planar graph
are moved to obtain a straightline 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 3connected
planar graph
has a drawing δ such that at most O((nlog n)2/3) vertices are fixed in every untangling of δ.
Journal:
Discrete & Computational Geometry  DCG
, vol. 43, no. 2, pp. 402411, 2010
DOI:
10.1007/s004540099150x
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
www.springerlink.com
)
(
www.springerlink.com
)
(
www.springerlink.com
)
(
www.springerlink.com
)
(
arxiv.org
)
More »
References
(14)
A combinatorial problem in geometry
(
Citations: 333
)
George Szekeres
On straight line representation of planar graphs
(
Citations: 147
)
I. Fary
Moving Vertices to Make Drawings Plane
(
Citations: 8
)
Xavier Goaoc
,
Jan Kratochvil
,
Yoshio Okamoto
,
ChanSu Shin
,
Alexander Wolff
Journal:
Computing Research Repository  CORR
, vol. abs/0706.1, pp. 101112, 2007
Untangling a Polygon
(
Citations: 17
)
János Pach
,
Gábor Tardos
Conference:
Symposium on Graph Drawing  GD
, pp. 154161, 2001
Untangling a Planar Graph
(
Citations: 11
)
Andreas Spillner
,
Alexander Wolff
Conference:
Conference on Current Trends in Theory and Practice of Informatics  SOFSEM
, pp. 473484, 2008
Sort by:
Citations
(1)
Untangling planar graphs from a specified vertex position  Hard cases
Mihyun Kang
,
Oleg Pikhurko
,
Alexander Ravsky
,
Mathias Schacht
,
Oleg Verbitsky
Journal:
Discrete Applied Mathematics  DAM
, vol. 159, no. 8, pp. 789799, 2011