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 grafos . 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 como se define tradicionalmente y sobre variaciones del número de cruce, seguido 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 introducir el problema, el primer capítulo estudia los números de cruce de grafos completos (incluyendo la fórmula conjeturada de Hill para estos números) y grafos bipartitos completos ( el problema de la fábrica de ladrillos de Turán y la conjetura del número de cruce de Zarankiewicz), dando de nuevo una fórmula conjeturada). [2] [3] También incluye la desigualdad del número de cruce y el teorema de Hanani-Tutte sobre la paridad de los cruces. [1] El segundo capítulo trata de otras clases especiales de grafos incluyendo productos de grafos (especialmente productos de grafos de ciclos ) y grafos de hipercubos . [2] [3] Después de un tercer capítulo que relaciona el número de cruce con parámetros de grafo incluyendo asimetría , ancho de bisección , grosor y (a través de la conjetura de Albertson ) el número cromático , el capítulo final de la parte I trata de la complejidad computacional de encontrar dibujos de grafos de cruce mínimo, incluyendo 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 tratan sobre el número de cruces rectilíneos, describiendo dibujos de grafos en los que las aristas deben representarse como segmentos de línea recta en lugar de curvas arbitrarias, y el teorema de Fáry que afirma que todo grafo plano puede dibujarse sin cruces de esta manera. Otro capítulo trata sobre grafos uniplanares y el número de cruces local asociado, el número k más pequeño tal que el grafo puede dibujarse con un máximo de k cruces por arista. Dos capítulos tratan sobre incrustaciones de libros y grafos de cadenas , y dos capítulos más tratan sobre 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 capítulo final de la parte II trata sobre los thrackles y el problema de encontrar dibujos con un número máximo de cruces. [2] [3]
El libro puede utilizarse como un libro de texto avanzado y cuenta con ejercicios previstos para ese uso. [2] [3] Sin embargo, 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 llama una "valiosa contribución" por su presentación de los numerosos resultados en esta área.