Algorithms for graphs embedded on surfaces

• Sergio Cabello ^[1]
  1. [1] University of Ljubljana

     University of Ljubljana

     Eslovenia

     
• Localización: XIII Encuentros de Geometría Computacional: Zaragoza, del 29 de junio al 1 de julio de 2009 / Alfredo García Olaverri (ed. lit.) , Javier Tejel Altarriba (ed. lit.) , 2009, ISBN 978-84-92774-11-1, págs. 35-41
• Idioma: inglés
• Texto completo no disponible (Saber más ...)
• Resumen

  • Graphs embedded on surfaces are a natural generalization of plane graphs. Any cycle in an embedded graph defines a closed curve in the surface and we can therefore consider topological properties of such curve. When the graph is equipped with edge-weights, we can also talk about the length of cycles. We will give an overview of the algorithms and techniques used to find shortest cycles with certain topological properties in embedded graphs, like for example a shortest non-contractible cycle.