Resumen

El número de cruce de un grafo es el número mínimo de aristas que se cruzan en cualquier dibujo de dicho grafo en un plano. En este documento describimos un método para encontrar el límite del número de cruce lineal de 2 páginas fijo de . Consideramos un grafo de conflicto de . En lugar de minimizar el número de cruce de , demostramos que es equivalente maximizar el peso de un corte de . Formulamos el problema original en el problema MAXCUT. Consideramos una relajación semidefinida del problema MAXCUT. Se muestra explícitamente un ejemplo de un caso donde es un hipercubo para obtener un límite superior. Los resultados numéricos confirman la efectividad de la aproximación.

• Materias:Modelo epidémico Ondas no lineales Métodos computacionales Ecuaciones integrales diferenciales Asignación de valores
• Subjects:Epidemic model Nonlinear waves Computational methods Differential integral equations Value assignment
• Palabras claves:Número de cruce; Grafo; Aristas; Dibujo; Plano; MAXCUT
• Keywords:Crossing number; Graph; Edges; Drawing; Plane; MAXCUT