*Note:*Please forgive me my formal imprecision. If anyone feels “offended” by this, she might want to read the papers instead.

are the eigenvectors and

the according eigenvalues of the laplacian matrix of the graph

sorted that

,

, the position vector for vertex

is

where

denotes the

th component of the eigenvector

.

denote the degree matrix [14] of the graph and

the adjency matrix, then the laplacian matrix is

. Now we may calculate the eigenvectors of

. The Octave code below loads some graph’s adjency matrix in text format and calculates the (first three) eigenvectors of the laplacian matrix (basically taken from [15]):

1 2 3 4 | load graph.txt; A = sparse(graph); L = diag(sum(A)) - A; [v,d] = eigs(L, 3, 'sm'); |

Then I plotted the graph using gnuplot (to be more precise: using gplot, Octaves built-in graph plotting functionality). The result was already pretty pleasing:

But I wanted things to look better, so I wrote a MEX file [16] which plotts graphs using OpenCV [17].

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 | #include "mex.h" #include <opencv/cv.h> #include <opencv/highgui.h> #define SCALE 40000 #define IN_ADJ prhs[0] #define IN_XY prhs[1] #define min(x,y) ((x) < (y) ? (x) : (y)) #define max(x,y) ((x) > (y) ? (x) : (y)) #define XY(i) (int)((xyOffset + xy[i]) * SCALE) void mexFunction (int nlhs, mxArray *plhs[], int nrhs, const mxArray *prhs[]) { if(nrhs < 2) mexErrMsgTxt("expects two parameters: adjency matrix (sparse, n times n), xy vector (n times 2)"); if(! mxIsSparse(IN_ADJ)) mexErrMsgTxt("Adjency matrix must be sparse"); if(mxGetM(IN_ADJ) != mxGetN(IN_ADJ)) mexErrMsgTxt("Adjency matrix must be square"); int n = mxGetN(IN_ADJ); int nz = mxGetNzmax(IN_ADJ); if(mxGetN(IN_XY) != 2 || mxGetM(IN_XY) != n) mexErrMsgTxt("XY vector must be (n times 2)"); double *xy = mxGetPr(IN_XY); double *adj = mxGetPr(IN_ADJ); // get dimensions int i, j; double xyOffset = 0, maxX = 0, maxY = 0; for(i = 0; i < n; i++) { if(xy[i] < xyOffset) xyOffset = xy[i]; if(xy[i] > maxX) maxX = xy[i]; } for(i = n; i < 2*n; i++) { if(xy[i] < xyOffset) xyOffset = xy[i]; if(xy[i] > maxY) maxY = xy[i]; } xyOffset = -xyOffset; maxX += xyOffset; maxY += xyOffset; mexPrintf("img size: %i x %i, xyOffset: %f, maxX: %f, maxY: %f\n", (int)(maxX * SCALE), (int)(maxY * SCALE), xyOffset, maxX, maxY); IplImage *img = cvCreateImage(cvSize((int)(maxX * SCALE), (int)(maxY * SCALE)), IPL_DEPTH_8U, 3); int *ir = mxGetIr(IN_ADJ); int *jc = mxGetJc(IN_ADJ); int total = 0; CvPoint p1, p2; for (i=0; i<n; i++) { p1.x = XY(i); p1.y = XY(n + i); int starting_row_index = jc[i]; int stopping_row_index = jc[i+1]; if (starting_row_index == stopping_row_index) continue; else { for (j = starting_row_index; j < stopping_row_index; j++) { p2.x = XY(ir[j]); p2.y = XY(n + ir[j]); cvLine(img, p1, p2, cvScalar(255,128,255,0), 1, CV_AA, 0); // mexPrintf("\t(%d,%d) = %g || (%i %i) -- (%i %i)\n", ir[j]+1, i+1, adj[total++], p1.x, p1.y, p2.x, p2.y); } } } if(!cvSaveImage("/tmp/gr.png", img)) mexErrMsgTxt("Unable to write /tmp/gr.png"); cvNamedWindow("mainWin", CV_WINDOW_AUTOSIZE); cvShowImage("mainWin", img ); cvWaitKey(20); } |

That code was used to produce the following graphs (except for the blue one, my WordPress simply can’t exclude images in a gallery):

With something looking that cool in my hands, I simply had to create posters out of that. So I postprocessed two graph images and ordered prints (the two black and white images). That stuff is fun, and extremly interessting. I’ll for sure do some further investigation on this topic.

## References

- [2] Dan Spielman's spectral graph theory site: http://www.cs.yale.edu/homes/spielman/sgta/
- [15] D. Spielman: Spectral Graph Theory and its Applications: http://www2.computer.org/portal/web/csdl/doi/10.1109/FOCS.2007.56
- [8] On Spectral Graph Drawing: http://www.springerlink.com/content/fpl2w4j6ug1aavyf/
- [5] Wikipedia: Eigenvectors: http://en.wikipedia.org/wiki/Eigenvectors
- [6] Wikipedia: Laplacian matrix: http://en.wikipedia.org/wiki/Laplacian_matrix
- [9] Wikipedia: planar graph: http://en.wikipedia.org/wiki/Planar_graph
- [10] Graph Partitioning - Graph Collection: http://wwwcs.upb.de/cs/ag-monien/RESEARCH/PART/graphs.html
- [11] PARTY Partitioning Library: http://wwwcs.uni-paderborn.de/fachbereich/AG/monien/RESEARCH/PART/party.html
- [12] Octave homepage: http://www.gnu.org/software/octave/
- [13] Wikipedia: ajency matrix: http://en.wikipedia.org/wiki/Adjacency_matrix
- [14] Wikipedia: degree matrix: http://en.wikipedia.org/wiki/Degree_matrix
- [16] Matlab: MEX-files Guide: http://www.mathworks.com/support/tech-notes/1600/1605.html
- [17] OpenCV homepage: http://opencv.willowgarage.com/