Número de cruce (teoría de grafos)

En teoría de grafos, el número de cruce cr(G), también llamado número de cruzamiento, de un grafo G es el menor numero de cruces de aristas en un diagrama plano del grafo G. Por ejemplo, un grafo es plano si y solo si su número de cruce es cero.El estudio de los números de cruce tuvo su origen en elproblema de la fábrica de ladrillos de Turán, en el cual Pál Turán buscó determinar el numero de cruce del grafo bipartito completo Km,n. Sin embargo, el mismo problema de minimizar cruces fue también considerado en sociología aproximadamente al mismo tiempo que Turán, en conexion con la construcción de sociogramas. Sigue siendo de gran importancia en diagramado de grafos.Sin otra especificación, el número de cruce permite diagramas en los que las aristas pueden ser representadas por curvas arbitrarias; el número de cruce rectilineo requiere que todas las aristas sean segmentos de línea recta, y puede diferir del número de cruce. En particular, el número de cruce rectilineo de un grafo completo es esencialmente el mismo que el número mínimo de cuadriláteros convexos determinados por un conjunto de ""n"" puntos en posición general, estrechamente relacionado con el Problema del final feliz.