A graph drawing is a representation of a graph, showing its vertices and egdes laid out in two (or three) dimensions in order for the graph structure to become visible. Graph drawings are easy to produce when a graph is small, and become harder to generate and less useful when a graph is larger.
Given a graph, a graph drawing can be specified by the placement of its vertices in the plane. To determine such a placement is a non-trivial problem, for which many algortihms exist, depending on the required properties of the drawing. For instance, each vertex should be placed near to its neighbors, vertices should not be drawn to near to each other, and edges should, if possible, not cross each other. It is clear that it is impossible to fulfill all these requirements at once, and thus no best graph drawing exists.
In KONECT, we show drawings of small graphs only, such that vertices and edges remain visible. The graph drawings in KONECT are spectral graph drawings, i.e., they are based on the eigenvectors of characteric graph matrices. In particular, KONECT included graph drawings based on the adjacency matrix \(\mathbf A\), the normalized adjacency matrix \(\mathbf N\) and the Laplacian matrix \(\mathbf L\). Let \(\mathbf x\) and \(\mathbf y\) be the two chosen eigenvector of each matrix, then the coordinate of the node \(u\in V\) is given by \(\mathbf x_u\) and \(\mathbf y_u\).
For the adjacency matrix \(\mathbf A\) and the normalized adjacency matrix \(\mathbf N\), we use the two eigenvector with largest absolute eigevalue. For the Laplacian matrix \(\mathbf L\), we use the two eigenvectors with smallest nonzero eigenvalue.