MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Kutz, Martindblp
Editor(s):
Amenta, Nina
Cheong, Otfried
dblp
dblp
Not MPII Editor(s):
Amenta, Nina
Cheong, Otfried
BibTeX cite key*:
Kutz2006
Title, Booktitle
Title*:
Computing Shortest Non-Trivial Cycles on Orientable Surfaces of Bounded Genus in Almost Linear Time.
Booktitle*:
Proceedings of the 22nd Annual Symposium on Computational Geometry, SCG'06
Event, URLs
Conference URL::
http://socg06.cs.arizona.edu/
Downloading URL:
Event Address*:
Sedona, Arizona, USA
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
5 June 2006
Event End Date:
7 June 2006
Publisher
Name*:
ACM
URL:
http://www.acm.org/
Address*:
New York, USA
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
Pages:
430-437
Year*:
2006
VG Wort Pages:
ISBN/ISSN:
1-59593-340-9
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
We present an algorithm that computes a shortest non-contractible and a shortest non-separating cycle on an orientable combinatorial surface of bounded
genus in $O(n log n)$ time, where $n$ denotes the complexity of the surface. This solves a central open problem in computational topology, improving
upon the current-best $O(n \frac{3}{2})$-time algorithm by Cabello and Mohar (ESA 2005).
Our algorithm is based on universal-cover constructions to find short cycles and makes extensive use of existing tools from the field.
Keywords:
computational topology, non-trivial cycles, efficient algorithm, planar graph, system of loops, universal cover
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Kutz2006,
AUTHOR = {Kutz, Martin},
EDITOR = {Amenta, Nina and Cheong, Otfried},
TITLE = {Computing Shortest Non-Trivial Cycles on Orientable Surfaces of Bounded Genus in Almost Linear Time.},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Computational Geometry, SCG'06},
PUBLISHER = {ACM},
YEAR = {2006},
PAGES = {430--437},
ADDRESS = {Sedona, Arizona, USA},
ISBN = {1-59593-340-9},
}


Entry last modified by Regina Kraemer, 04/16/2007
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Pascal Schweitzer
Created
02/28/2007 01:03:49 PM
Revisions
3.
2.
1.
0.
Editor(s)
Regina Kraemer
Christine Kiesel
Pascal Schweitzer
Pascal Schweitzer
Edit Dates
04/16/2007 09:56:47 AM
12.03.2007 08:00:47
02/28/2007 01:06:52 PM
02/28/2007 01:03:49 PM