Computing shortest cycles using universal covering space

Xiaotian Yin; Miao Jin; Xianfeng Gu

doi:10.1109/CADCG.2007.4407839

Computing shortest cycles using universal covering space

Xiaotian Yin
, Miao Jin
, Xianfeng Gu

Computer Science

Stony Brook University

Stony Brook University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

3 Scopus citations

Abstract

In this paper we generalize the shortest path algorithm to the shortest cycles in each homotopy class on a surface with arbitrary topology, utilizing the universal covering space (UCS) in algebraic topology. In order to store and handle the UCS, we propose a two-level data structure which is efficient for storage and easy to process. We also pointed several practical applications for our shortest cycle algorithms and the UCS data structure.

Original language	English
Title of host publication	Proceedings of 2007 10th IEEE International Conference on Computer Aided Design and Computer Graphics, CAD/Graphics 2007
Pages	25
Number of pages	1
DOIs	https://doi.org/10.1109/CADCG.2007.4407839
State	Published - 2007
Event	2007 10th IEEE International Conference on Computer Aided Design and Computer Graphics, CAD/Graphics 2007 - Beijing, China Duration: Oct 15 2007 → Oct 18 2007

Publication series

Name	Proceedings of 2007 10th IEEE International Conference on Computer Aided Design and Computer Graphics, CAD/Graphics 2007

Conference

Conference	2007 10th IEEE International Conference on Computer Aided Design and Computer Graphics, CAD/Graphics 2007
Country/Territory	China
City	Beijing
Period	10/15/07 → 10/18/07

Access to Document

10.1109/CADCG.2007.4407839

Cite this

Yin, X., Jin, M., & Gu, X. (2007). Computing shortest cycles using universal covering space. In Proceedings of 2007 10th IEEE International Conference on Computer Aided Design and Computer Graphics, CAD/Graphics 2007 (pp. 25). Article 4407839 (Proceedings of 2007 10th IEEE International Conference on Computer Aided Design and Computer Graphics, CAD/Graphics 2007). https://doi.org/10.1109/CADCG.2007.4407839

@inproceedings{34f9da2f46564accbe35f315c6d602a8,

title = "Computing shortest cycles using universal covering space",

abstract = "In this paper we generalize the shortest path algorithm to the shortest cycles in each homotopy class on a surface with arbitrary topology, utilizing the universal covering space (UCS) in algebraic topology. In order to store and handle the UCS, we propose a two-level data structure which is efficient for storage and easy to process. We also pointed several practical applications for our shortest cycle algorithms and the UCS data structure.",

author = "Xiaotian Yin and Miao Jin and Xianfeng Gu",

year = "2007",

doi = "10.1109/CADCG.2007.4407839",

language = "English",

isbn = "9781424415793",

series = "Proceedings of 2007 10th IEEE International Conference on Computer Aided Design and Computer Graphics, CAD/Graphics 2007",

pages = "25",

booktitle = "Proceedings of 2007 10th IEEE International Conference on Computer Aided Design and Computer Graphics, CAD/Graphics 2007",

note = "2007 10th IEEE International Conference on Computer Aided Design and Computer Graphics, CAD/Graphics 2007 ; Conference date: 15-10-2007 Through 18-10-2007",

}

Yin, X, Jin, M & Gu, X 2007, Computing shortest cycles using universal covering space. in Proceedings of 2007 10th IEEE International Conference on Computer Aided Design and Computer Graphics, CAD/Graphics 2007., 4407839, Proceedings of 2007 10th IEEE International Conference on Computer Aided Design and Computer Graphics, CAD/Graphics 2007, pp. 25, 2007 10th IEEE International Conference on Computer Aided Design and Computer Graphics, CAD/Graphics 2007, Beijing, China, 10/15/07. https://doi.org/10.1109/CADCG.2007.4407839

Computing shortest cycles using universal covering space. / Yin, Xiaotian; Jin, Miao; Gu, Xianfeng.
Proceedings of 2007 10th IEEE International Conference on Computer Aided Design and Computer Graphics, CAD/Graphics 2007. 2007. p. 25 4407839 (Proceedings of 2007 10th IEEE International Conference on Computer Aided Design and Computer Graphics, CAD/Graphics 2007).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Computing shortest cycles using universal covering space

AU - Yin, Xiaotian

AU - Jin, Miao

AU - Gu, Xianfeng

PY - 2007

Y1 - 2007

N2 - In this paper we generalize the shortest path algorithm to the shortest cycles in each homotopy class on a surface with arbitrary topology, utilizing the universal covering space (UCS) in algebraic topology. In order to store and handle the UCS, we propose a two-level data structure which is efficient for storage and easy to process. We also pointed several practical applications for our shortest cycle algorithms and the UCS data structure.

AB - In this paper we generalize the shortest path algorithm to the shortest cycles in each homotopy class on a surface with arbitrary topology, utilizing the universal covering space (UCS) in algebraic topology. In order to store and handle the UCS, we propose a two-level data structure which is efficient for storage and easy to process. We also pointed several practical applications for our shortest cycle algorithms and the UCS data structure.

UR - https://www.scopus.com/pages/publications/48149094731

U2 - 10.1109/CADCG.2007.4407839

DO - 10.1109/CADCG.2007.4407839

M3 - Conference contribution

SN - 9781424415793

T3 - Proceedings of 2007 10th IEEE International Conference on Computer Aided Design and Computer Graphics, CAD/Graphics 2007

SP - 25

BT - Proceedings of 2007 10th IEEE International Conference on Computer Aided Design and Computer Graphics, CAD/Graphics 2007

T2 - 2007 10th IEEE International Conference on Computer Aided Design and Computer Graphics, CAD/Graphics 2007

Y2 - 15 October 2007 through 18 October 2007

ER -

Yin X, Jin M, Gu X. Computing shortest cycles using universal covering space. In Proceedings of 2007 10th IEEE International Conference on Computer Aided Design and Computer Graphics, CAD/Graphics 2007. 2007. p. 25. 4407839. (Proceedings of 2007 10th IEEE International Conference on Computer Aided Design and Computer Graphics, CAD/Graphics 2007). doi: 10.1109/CADCG.2007.4407839

Computing shortest cycles using universal covering space

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this