Spektral layout
Spektral layout är en klass av algoritmer för att rita grafer . Layouten använder egenvektorerna för en matris, såsom grafens Laplace-matris , som kartesiska koordinater för grafens hörn.
Tanken med layouten är att beräkna de två största (eller minsta) egenvärdena och motsvarande egenvektorer för grafens Laplacian-matris och sedan använda dem för att faktiskt placera noderna. Vanligtvis placeras noder i det tvådimensionella planet. En inbäddning i fler dimensioner kan hittas genom att använda fler egenvektorer. I det 2-dimensionella fallet, för en given nod som motsvarar raden/kolumnen i den (symmetriska) Laplacian-matrisen i grafen, och -koordinater är de -th ingångarna i den första respektive andra egenvektorn för .
- Beckman, Brian (1994), Theory of Spectral Graph Layout, Tech. Rapport MSR-TR-94-04, Microsoft Research .
- Koren, Yehuda (2005), "Drawing graphs by eigenvectors: theory and practice", Computers & Mathematics with Applications , 49 (11–12): 1867–1888, doi : 10.1016 /j.camwa.2004.08.021 , 469 1 .