Carregant...
Carregant...

Vés al contingut (premeu Retorn)

On Hamiltonian alternating cycles and paths

Autor
Claverol, M.; Garcia, A.; Garijo, D.; Seara, C.; Tejel, F.
Tipus d'activitat
Presentació treball a congrés
Nom de l'edició
XVI Spanish Meeting on Computational Geometry
Any de l'edició
2015
Data de presentació
2015-07-01
Llibre d'actes
XVI Spanish meeting of computational geometry: Barcelona : July 1-3, 2015: proceedings book
Pàgina inicial
5
Pàgina final
8
Repositori
http://www-ma2.upc.es/egc15/wp-content/uploads/2013/10/AbstractsXVIEGC.pdf Obrir en finestra nova
Resum
A natural relaxation for problems that have no solution for plane geometric graphs is to allow the geometric graphs to be 1-plane, that is, there can be at most one crossing per edge. In this work, we study this relaxation for Hamiltonian alternating cycles and paths. Thus, it is well-known that one cannot always draw a plane Hamiltonian alternating cycle, even on a bicolored point set in convex position, whilst we prove that allowing the cycle to be 1-plane, it can always be found, on a point s...
Paraules clau
Bicolored Point Sets, Hamiltonian, Alternating, 1-plane, Cycle, Path.
Grup de recerca
DCCG - Grup de recerca en geometria computacional, combinatoria i discreta

Participants

  • Claverol Aguas, Merce  (autor ponent)
  • Garcia Olaverri, Alfredo Martin  (autor ponent)
  • Garijo Royo, Delia  (autor ponent)
  • Seara Ojea, Carlos  (autor ponent)
  • Tejel Altarriba, Francisco Javier  (autor ponent)