Re: Drawing graphs by hand

From: Stephen M. Fortescue (sfortescue_at_adelphia.net)
Date: 01/31/05 

Date: 30 Jan 2005 21:21:04 -0800

johngcarlsson@gmail.com wrote:
> Hi there,
> I have been drawing a lot of graphs by hand lately, and I was
> wondering if anybody knew any useful "by hand" graph layout
> algorithms, so to speak. All of the actual graph layout algorithms
> for computers are far too complicated to do on paper it seems,
> so I was wondering if anybody has good rules of thumb for drawing
> graphs and making them look somewhat reasonable. Thanks!

When drawing small graphs by hand, you should give priority
to smaller circuits. Being able to see the arrangement of triangles
is more important than of quadrangles, etc.

You can get some hint of how to arrange a somewhat larger graph by
computing the eigenvectors of its Laplacian matrix. The vectors
associated with the smallest non-zero eigenvalues can be used
as coordinates for plotting the vertices. If you imagine the graph
as being made out of springs and masses, the eigenvalues are
proportional to the squares of the oscillating frequencies.

If the graph is highly symmetrical and the smallest eigenvalue has
high multiplicity, finding sets of vertices that connect in the same
way to vertices in other sets, thus drawing a distribution diagram,
can be helpful. Eigenvectors can be computed from the distribution
matrix which describes the diagram.

This distribution matrix is of Sylvester's double-six graph:

' A B C D 5 2 -1 -3

A 1 ' 5 ' ' 1 20 5 5
B 5 1 ' 4 ' 1 8 -1 -3
C 20 ' 1 2 2 1 -1 -1 1
D 10 ' ' 4 1 1 -4 2 -1

' 1 16 10 9

The single "A" vertex connects to all 5 "B" vertices.
Each "B" vertex connects to 4 of the "C" vertices, etc.

To the right are the eigenvectors with eigenvalues above and
multiplicities below. Since this is a regular graph, subtract
these eigenvalues (of the adjacency matrix) from the degree
to get the eigenvalues of the Laplacian matrix. (Or, if not regular,
subtract the matrix from a diagonal matrix formed from the row sums
to get the Laplacian matrix before solving.)

The multiplicities show that the graph can be drawn with full
symmetry in 16-dimensional space (or 10 or 9 with more tangling).

A starting partition that selects 2 individual vertices which
are at distance 3 from each other gives this:

' A B C D E F G H J K L M 2 2 2 2

A 1 ' 1 4 ' ' ' ' ' ' ' ' ' 4 4 4 0
B 1 1 ' ' 4 ' ' ' ' ' ' ' ' 4 4 -4 0
C 4 1 ' ' ' 1 1 ' ' 1 1 ' ' 1 1 3 0
D 4 ' 1 ' ' ' ' 1 1 1 1 ' ' 1 1 -3 0

E 4 ' ' 1 ' ' 1 1 1 1 ' ' ' -2 0 1 1
F 4 ' ' 1 ' 1 ' 1 1 ' 1 ' ' -2 0 1 -1
G 4 ' ' ' 1 1 1 ' 1 1 ' ' ' -2 0 -1 1
H 4 ' ' ' 1 1 1 1 ' ' 1 ' ' -2 0 -1 -1

J 4 ' ' 1 1 1 ' 1 ' ' ' 1 ' 1 -1 0 3
K 4 ' ' 1 1 ' 1 ' 1 ' ' ' 1 1 -1 0 -3
L 1 ' ' ' ' ' ' ' ' 4 ' ' 1 4 -4 0 4
M 1 ' ' ' ' ' ' ' ' ' 4 1 ' 4 -4 0 -4

' 144 80 120 120

With only 4 dimensions, this is more manageable. Below the vectors
are the norms. Scale to make the norms equal before using these as
coordinates in 4-dimensional space.

Relevant Pages

  • Quantum Gravity 170.98: Eigenvalue Symmetry About 0 in Graph Theory
    ... Take a look at Wikipedia's "Graph theory," which defines adjacency ... A Laplacian matrix is defined as degree matrix - adjacency ... Next consider "Integer symmetric matrices having all their eigenvalues ...
    (sci.physics)
  • Re: (graph theory: path problem)how to tell how many path are there from s to t in a graph?
    ... diagonal entries of A^3 will only be nonzero in the case that there exists ... a triangle in the graph, ... keeps the eigenvalues of the adjacency (called the "spectrum" of a graph, ... And counting non-simple paths, you get: ...
    (comp.theory)
  • Re: Changes in Eigenvalues related to graphs
    ... to a graph affects eigenvalues of matrices associated with graph -such ... of the symmetric adjacency matrix by one, ... Eigenvalues of the adjacency matrix of tetrahedral graphs (English) ...
    (sci.math.num-analysis)
  • Re: eigenvalues of adjacency matrix
    ... general result about the eigenvalues of the adjacency matrix of a ... graph. ... eigenvalues of a matrix whose entries are in?. ... and Sachs ("Spectra of Graphs: ...
    (sci.math.research)
  • Re: Standard graph API?
    ... How would the algorithms work without a standard API? ... [code generating template example snipped] ... Well -- I was rather aiming for a definition of a graph protocol ...
    (comp.lang.python)