Carregant...
Carregant...

Vés al contingut (premeu Retorn)

Geometric biplane graphs I: maximal graphs

Autor
Garcia, A.; Hurtado, F.; Korman, M.; Matos, I. P.; Saumell, M.; Silveira, R.I.; Tejel, F.; Tóth, C.D.
Tipus d'activitat
Article en revista
Revista
Graphs and combinatorics
Data de publicació
2015-03-01
Volum
31
Número
2
Pàgina inicial
407
Pàgina final
425
DOI
https://doi.org/10.1007/s00373-015-1546-1 Obrir en finestra nova
Projecte finançador
Puntos y grafos: puentes geométricos (IP04 en CRP Comb. of points sets, ComPoSe,EuroGIGA ESF)
Repositori
http://hdl.handle.net/2117/80896 Obrir en finestra nova
Resum
We study biplane graphs drawn on a finite planar point set in general position. This is the family of geometric graphs whose vertex set is and can be decomposed into two plane graphs. We show that two maximal biplane graphs-in the sense that no edge can be added while staying biplane-may differ in the number of edges, and we provide an efficient algorithm for adding edges to a biplane graph to make it maximal. We also study extremal properties of maximal biplane graphs such as the maximum number...
Citació
Garcia, A., Hurtado, F., Korman, M., Matos, I. P., Saumell, M., Silveira, R.I., Tejel, F., Tóth, C.D. Geometric biplane graphs I: maximal graphs. "Graphs and combinatorics", 01 Març 2015, vol. 31, núm. 2, p. 407-425.
Paraules clau
Biplane graphs, Connectivity, Geometric graphs, Graph augmentation, Maximal biplane graphs, Planar graphs, k-Connected graphs
Grup de recerca
CGA -Computational Geometry and Applications

Participants

  • Garcia Olaverri, Alfredo Martin  (autor)
  • Hurtado Diaz, Fernando Alfredo  (autor)
  • Korman Cozzetti, Matias  (autor)
  • Matos, Inés P.  (autor)
  • Saumell, Maria  (autor)
  • Silveira, Rodrigo Ignacio  (autor)
  • Tejel Altarriba, Francisco Javier  (autor)
  • Tóth, Csaba D.  (autor)

Arxius