Version française


Guillaume Damiand

oHome page

oResearches

oPublications

oTeaching

oSupervised Thesis

oCV

oContacts

oLinks

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

Links:  PDF  Hal  Link  

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}
}

Image


o [Back]