Familias de cruce de gráficas geométricas completas

Autor: Christian Rubio Montiel
Coautor(es): Dolores Lara
Una gráfica geométrica es una gráfica dibujada en el plano tal que sus n vértices están en posición general, y sus aristas son segmentos de línea rectilíneos. Dos subgráficas geométricas se cruzan si existe una arista en la primer subgráfica y una arista en la segunda subgráfica con un cruce, es decir, con un punto interior en común. Una familia de subgráficas geométricas arista-disjuntas se llama de cruce mútuo si cualesquiera dos de sus elementos se cruzan. Mostraremos que para cualquier gráfica completa geométrica siempre existe una familia de cruce mútuo de 2-trayectorias (trayectorias de longitud 2) de al menos (n/2+1)^0.5-1 elementos, y una familia de cruce mútuo de 3-estrellas (estrellas de 3 hojas) de al menos n/6 elementos.