Publication

Computational Complexity of Combinatorial Surfaces

Vegter, G. & Yap, C. K., 1990, EPRINTS-BOOK-TITLE. University of Groningen, Johann Bernoulli Institute for Mathematics and Computer Science, 10 p.

Research output: Chapter in Book/Report/Conference proceedingChapterAcademic

APA

Vegter, G., & Yap, C. K. (1990). Computational Complexity of Combinatorial Surfaces. In EPRINTS-BOOK-TITLE University of Groningen, Johann Bernoulli Institute for Mathematics and Computer Science.

Author

Vegter, Gert ; Yap, Chee K. / Computational Complexity of Combinatorial Surfaces. EPRINTS-BOOK-TITLE. University of Groningen, Johann Bernoulli Institute for Mathematics and Computer Science, 1990.

Harvard

Vegter, G & Yap, CK 1990, Computational Complexity of Combinatorial Surfaces. in EPRINTS-BOOK-TITLE. University of Groningen, Johann Bernoulli Institute for Mathematics and Computer Science.

Standard

Computational Complexity of Combinatorial Surfaces. / Vegter, Gert; Yap, Chee K.

EPRINTS-BOOK-TITLE. University of Groningen, Johann Bernoulli Institute for Mathematics and Computer Science, 1990.

Research output: Chapter in Book/Report/Conference proceedingChapterAcademic

Vancouver

Vegter G, Yap CK. Computational Complexity of Combinatorial Surfaces. In EPRINTS-BOOK-TITLE. University of Groningen, Johann Bernoulli Institute for Mathematics and Computer Science. 1990


BibTeX

@inbook{2f3bd8b0e11c4dfa89eef0fe5f452941,
title = "Computational Complexity of Combinatorial Surfaces",
abstract = "We investigate the computational problems associated with combinatorial surfaces. Specifically, we present an algorithm (based on the Brahana-Dehn-Heegaard approach) for transforming the polygonal schema of a closed triangulated surface into its canonical form in O(n log n) time, where n is the total number of vertices, edges and faces. We also give an O(n log n + gn) algorithm for constructing canonical generators of the fundamental group of a surface of genus g. This is useful in constructing homeomorphisms between combinatorial surfaces.",
author = "Gert Vegter and Yap, {Chee K.}",
note = "Relation: https://www.rug.nl/informatica/organisatie/overorganisatie/iwi Rights: University of Groningen. Research Institute for Mathematics and Computing Science (IWI)",
year = "1990",
language = "English",
booktitle = "EPRINTS-BOOK-TITLE",
publisher = "University of Groningen, Johann Bernoulli Institute for Mathematics and Computer Science",

}

RIS

TY - CHAP

T1 - Computational Complexity of Combinatorial Surfaces

AU - Vegter, Gert

AU - Yap, Chee K.

N1 - Relation: https://www.rug.nl/informatica/organisatie/overorganisatie/iwi Rights: University of Groningen. Research Institute for Mathematics and Computing Science (IWI)

PY - 1990

Y1 - 1990

N2 - We investigate the computational problems associated with combinatorial surfaces. Specifically, we present an algorithm (based on the Brahana-Dehn-Heegaard approach) for transforming the polygonal schema of a closed triangulated surface into its canonical form in O(n log n) time, where n is the total number of vertices, edges and faces. We also give an O(n log n + gn) algorithm for constructing canonical generators of the fundamental group of a surface of genus g. This is useful in constructing homeomorphisms between combinatorial surfaces.

AB - We investigate the computational problems associated with combinatorial surfaces. Specifically, we present an algorithm (based on the Brahana-Dehn-Heegaard approach) for transforming the polygonal schema of a closed triangulated surface into its canonical form in O(n log n) time, where n is the total number of vertices, edges and faces. We also give an O(n log n + gn) algorithm for constructing canonical generators of the fundamental group of a surface of genus g. This is useful in constructing homeomorphisms between combinatorial surfaces.

M3 - Chapter

BT - EPRINTS-BOOK-TITLE

PB - University of Groningen, Johann Bernoulli Institute for Mathematics and Computer Science

ER -

ID: 3354077