As I recall, Miller's planarity algorithm didn't work on the adjacency matrix, but was pretty purely graph-theoretic: it ran around the graph identifying faces, arranging edges into cyclic order. I'm pretty sure I still have his paper, and I can check if I remember. On Fri, Oct 22, 2010 at 1:24 PM, Daniel Asimov <dasimov@earthlink.net>wrote:

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

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun