Computing Canonical Polygonal Schemata with Generalized Maps

Damiand G., Alayrangues S.

Proc. of International Conference on Topological & Geometric Graph Theory (TGGT)
Electronic Notes in Discrete Mathematics 31, pages 287-292, August 2008, Paris, France

Abstract: The comparison of two topological surfaces is a frequent question that may be solved by using accurate topological invariants. Such invariants already exist and the main difficulty is to achieve their computation efficiently. In [VegYap90], authors propose an algorithm which allows to compute the canonical polygonal schema of a given surface by using particular transformation rules. This paper shows that these transformations can be defined on a 2-dimensional generalized map which encodes a surface. The algorithm proposed in [VegYap90] to compute canonical polygonal schema can now be transfered onto generalized maps. Moreover, all transformations can be achieved in O(1) with generalized maps, which can help optimizing existing algorithms.

Keywords: Canonical polygon schema; Generalized maps; Topological invariant.

BibTex references

@InProceedings{DA08,
      author = {Damiand, G. and Alayrangues, S.},
      title = {Computing Canonical Polygonal Schemata with Generalized Maps},
      booktitle = {Proc. of International Conference on Topological \& Geometric Graph Theory (TGGT)},
      series = {Electronic Notes in Discrete Mathematics},
      publisher = {Elsevier},
      volume = {31},
      pages = {287-292},
      month = {August},
      year = {2008},
      address = {Paris, France},
      keywords = {Canonical polygon schema; Generalized maps; Topological invariant.},
      url = {https://doi.org/10.1016/j.endm.2008.06.058}
}

Guillaume Damiand

Computing Canonical Polygonal Schemata with Generalized Maps

Links:

BibTex references

Image