Cruces Rectilíneos sobre Gráficas Completas

El documento comienza abordando la complejidad del problema de determinar si una gráfica puede ser dibujada en un plano sin que sus aristas se intersequen. Específicamente, se centra en el caso de las gráficas completas, donde todas las aristas conectan todos los vértices. El objetivo es encontrar el mínimo número de intersecciones al dibujar una gráfica completa en el plano, donde las aristas se representan como segmentos de recta. La introducción destaca la relevancia de este problema en áreas como el diseño de circuitos, donde la minimización de cruces en los cables es crucial para la eficiencia y la funcionalidad.

El trabajo establece una conexión profunda entre el problema de los cruces rectilíneos y otros problemas en geometría combinatoria. Se explora la relación con el problema de los cuadriláteros convexos, que consiste en encontrar la distribución de puntos en un plano que minimice la probabilidad de encontrar cuadriláteros convexos. Se demuestra que la existencia de un cuadrilátero convexo formado por cuatro puntos en un conjunto equivale a la presencia de una intersección entre las aristas que forman esos puntos. Además, se relaciona el problema con el problema de los cuatro puntos de Sylvester, donde se busca minimizar la probabilidad de que cuatro puntos elegidos al azar formen un cuadrilátero convexo.

Para analizar el problema de los cruces rectilíneos, el documento introduce conceptos como k-conjuntos, k-aristas y rectas medianas. Los k-conjuntos son subconjuntos de un conjunto de puntos en el plano, y las k-aristas son segmentos de recta que conectan puntos en un k-conjunto. Las rectas medianas son líneas que pasan por dos puntos y dividen el resto del conjunto en dos subconjuntos de tamaño similar. Se establece una relación entre la cantidad de k-aristas y el número de cruces rectilíneos, mostrando cómo la existencia de k-aristas contribuye al número total de intersecciones. Se analiza el problema de las rectas medianas y se presenta una cota inferior para este problema, la cual se utiliza para obtener una cota inferior para el número de cruces rectilíneos.

El documento presenta algoritmos para calcular el número de cruces rectilíneos en una gráfica completa. Se describe un algoritmo con complejidad O(n^2 log(n)) que se basa en calcular las intersecciones entre las aristas de la gráfica. Se presenta otro algoritmo con una complejidad amortizada de O(n log(n)) que permite analizar el número de cruces rectilíneos al mover un punto a diferentes posiciones en el plano. Además, se describen dos heurísticas para la construcción de dibujos de gráficas completas con un bajo número de cruces rectilíneos. Estas heurísticas buscan generar conjuntos de puntos que tengan una gran cantidad de rectas medianas, lo que se ha demostrado que reduce la cantidad de intersecciones en los dibujos.