Disposición espectral

El diseño espectral es una clase de algoritmo para dibujar gráficos . El diseño utiliza los vectores propios de una matriz, como la matriz de Laplace del gráfico, como coordenadas cartesianas de los vértices del gráfico.

La idea del diseño es calcular los dos valores propios más grandes (o más pequeños) y los vectores propios correspondientes de la matriz laplaciana del gráfico y luego usarlos para ubicar los nodos. Por lo general, los nodos se ubican en el plano bidimensional. Se puede encontrar una incrustación en más dimensiones utilizando más vectores propios. En el caso bidimensional, para un nodo dado que corresponde a la fila/columna en la matriz laplaciana (simétrica) del gráfico, las coordenadas y son las entradas -ésimas del primer y segundo vector propio de , respectivamente. ${\displaystyle i}$${\displaystyle L}$${\displaystyle x}$${\displaystyle y}$${\displaystyle i}$${\displaystyle L}$

• Beckman, Brian (1994), Teoría del diseño de gráficos espectrales, Informe técnico MSR-TR-94-04, Microsoft Research.
• Koren, Yehuda (2005), "Dibujo de gráficos por vectores propios: teoría y práctica", Computers & Mathematics with Applications , 49 (11–12): 1867–1888, doi :10.1016/j.camwa.2004.08.015, MR  2154691.