P.S. Let's see: the planarity criterion is that the graph must not contain a subset that is topologically either the water-gas-electricity graph K(3,3) or the complete graph K(5) on 5 nodes. Hmm, so I wonder how this criterion may be reflected in the invariants of the graph's connectivity matrix. These graphs K(3,3) and K(5) have connectivity matrices: 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 and 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 and one or the other of these would have to be -- roughly speaking -- a submatrix of any non-planar graph. But I'm too rushed to figure out their eigenvalues right now. --Dan Henry wrote: << . . . Interestingly, _planar graphs_ play a part in this paper! Who knew that linear algebra & planar graphs were connected ? . . .
_____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele