Carregant...
Carregant...

Vés al contingut (premeu Retorn)

Lower bounds on the maximum number of non-crossing acyclic graphs

Autor
Huemer, C.; De Mier, A.
Tipus d'activitat
Article en revista
Revista
European journal of combinatorics
Data de publicació
2015-08-01
Volum
48
Número
C
Pàgina inicial
48
Pàgina final
62
DOI
https://doi.org/10.1016/j.ejc.2015.02.008 Obrir en finestra nova
Projecte finançador
Combinatoria, teoría de grafos y geometría discreta
Morfología geométrica computacional.
Puntos y grafos: puentes geométricos (IP04 en CRP Comb. of points sets, ComPoSe,EuroGIGA ESF)
Repositori
http://hdl.handle.net/2117/86044 Obrir en finestra nova
Resum
This paper is a contribution to the problem of counting geometric graphs on point sets. More concretely, we look at the maximum numbers of non-crossing spanning trees and forests. We show that the so-called double chain point configuration of N points has Omega (12.52(N)) non-crossing spanning trees and Omega (13.61(N)) non-crossing forests. This improves the previous lower bounds on the maximum number of non-crossing spanning trees and of non-crossing forests among all sets of N points in gener...
Citació
Huemer, C., De Mier, A. Lower bounds on the maximum number of non-crossing acyclic graphs. "European journal of combinatorics", 01 Agost 2015, vol. 48, núm. C, p. 48-62.
Grup de recerca
DCCG - Grup de recerca en geometria computacional, combinatoria i discreta
MD - Matemàtica Discreta

Participants

Arxius