(Suponiendo que se refiere al código, ya que etiquetó esta pregunta con “Algoritmos” …)
Puede usar el algoritmo Chrobak-Payne para generar un dibujo lineal del gráfico: el dibujo implica una incrustación plana.
No menciona en qué idioma o plataforma desea hacer esto, pero suponiendo que C ++, la biblioteca de gráficos de impulso incluye una implementación de Chrobak-Payne. El algoritmo solo funciona en gráficos planos máximos, pero esto no es un problema en la práctica; citando la documentación de impulso:
- ¿Necesito conocer algoritmos de aprendizaje automático para asegurar un trabajo como analista de datos?
- ¿Cuáles son las ventajas de los algoritmos SVM?
- ¿Hay alguna manera / hay algoritmos para dividir los caracteres chinos en radicales?
- ¿Existe un algoritmo para resolver el problema de la mochila 0/1 acotada multidimensional en PTIME?
- ¿Es posible el algoritmo de compresión que se muestra en Silicon Valley en realidad?
Tenga en cuenta que la restricción de que el gráfico sea máximo plano no significa que esta función solo pueda dibujar gráficos planos máximos […] Si desea dibujar un gráfico g , puede crear una copia g ‘ de g , almacenar un mapeo m de vértices en g ‘ a vértices en g , triangule g’ y luego envíe g ‘ como entrada para chrobak_payne_straight_line_drawing. El dibujo devuelto se puede aplicar a g usando m para traducir vértices de un gráfico a otro, ya que g contiene un subconjunto de los bordes en g ‘ .