Crossing Numbers of Graphs es un libro de matemáticas sobre el número mínimo de cruces de aristas necesarios en los dibujos de gráficos . Fue escrito por Marcus Schaefer, profesor de informática en la Universidad DePaul , y publicado en 2018 por CRC Press en su serie de libros Discrete Mathematics and its Applications.
El texto principal del libro tiene dos partes, sobre el número de cruce tal como se define tradicionalmente y sobre las variaciones del número de cruce, seguidas de dos apéndices [1] que proporcionan material de referencia sobre la teoría de grafos topológicos y la teoría de la complejidad computacional . [2]
Después de presentar el problema, el primer capítulo estudia los números de cruce de gráficos completos (incluida la fórmula conjeturada de Hill para estos números) y gráficos bipartitos completos ( el problema de la fábrica de ladrillos de Turán y la conjetura del número de cruce de Zarankiewicz), dando nuevamente una fórmula conjeturada). [2] [3] También incluye la desigualdad del número de cruces y el teorema de Hanani-Tutte sobre la paridad de cruces. [1] El segundo capítulo se refiere a otras clases especiales de gráficos, incluidos productos gráficos (especialmente productos de gráficos cíclicos ) y gráficos de hipercubo . [2] [3] Después de un tercer capítulo que relaciona el número de cruce con parámetros gráficos que incluyen asimetría , ancho de bisección , espesor y (a través de la conjetura de Albertson ) el número cromático , el capítulo final de la parte I se refiere a la complejidad computacional de encontrar mínimos. dibujos de gráficos cruzados, incluidos los resultados de que el problema es tanto NP-completo como manejable con parámetros fijos . [1] [2] [3]
En la segunda parte del libro, dos capítulos se ocupan del número de cruces rectilíneos, describiendo dibujos de gráficos en los que los bordes deben representarse como segmentos de línea recta en lugar de curvas arbitrarias, y el teorema de Fáry de que todo gráfico plano se puede dibujar sin cruces de esta manera. . Otro capítulo se ocupa de los gráficos uniplanares y el número de cruce local asociado, el número más pequeño k tal que el gráfico se pueda dibujar con como máximo k cruces por arista. Dos capítulos se refieren a incrustaciones de libros y gráficos de cadenas , y dos capítulos más se refieren a variaciones del número de cruces que cuentan los cruces de diferentes maneras, por ejemplo, por el número de pares de aristas que se cruzan o que se cruzan un número impar de veces. El último capítulo de la parte II trata sobre los grilletes y el problema de encontrar dibujos con un número máximo de cruces. [2] [3]
El libro se puede utilizar como libro de texto avanzado y contiene ejercicios para ese uso. [2] [3] Sin embargo, se supone que sus lectores ya están familiarizados tanto con la teoría de grafos como con el diseño y análisis de algoritmos . [2] Al revisar el libro, LW Beineke lo califica como una "valiosa contribución" por la presentación de los numerosos resultados en esta área.