Sign in to follow this  
Nick of ZA

Canonical form of a matrix, for planarity testing

Recommended Posts

This question is really about matrices more than about graphs, however it relates to the concept of planarity testing in graph, so anyone with the knowledge of the former, please don't be put off and read on... Given a graph G, in order to test conclusively for non-planarity, we reduce G (G') to find minimal isomorphic subgraphs, and then isolate one of the Kuratoswki subgraphs K5 or K3,3. One of the benefits of encoding a graph as an adjacency matrix is that we can perform equality comparisons, i.e. we test equality of the matrix of a given clique in G against the matrix representing K5 or K3,3. Isolating K5 is trivial; due to it's connectivity it only ever exists as a single matrix permutation -- the inverse of the 5x5 identity matrix, incidentally. My problem lies in finding a means to isolate K3,3 (the complete bipartite graph on 3 vertices). As a result of variable vertex ordering in K3,3, there are 10 individual permutations I've isolated that would need to be matched against. Here is an example of just 2 permutations, to give you a base on which to visualise the problem. Fig.1. {v1, v2, v3} is one half of the bipartite graph, {v4, v5, v6} the other: v 1 2 3 4 5 6 1 0 0 0 1 1 1 2 0 0 0 1 1 1 3 0 0 0 1 1 1 4 1 1 1 0 0 0 5 1 1 1 0 0 0 6 1 1 1 0 0 0 Fig.2. {v1, v4, v5} is one half of the bipartite graph, {v2, v3, v5} the other: v 1 2 3 4 5 6 1 0 1 1 0 1 0 2 1 0 0 1 0 1 3 1 0 0 1 0 1 4 0 1 1 0 1 0 5 0 1 1 0 1 0 6 1 0 0 1 0 1 Rather than testing against 10 separate permutations on every pertinent clique, I want to know if there is any way to derive some "canonical form", if you will, a single form that represents all ten combinations of vertex orderings. If I leave it at this, worst case scenario there are ten checks against precalculated matrices. But if I can get access to a canonical form, I can then convert the given clique's matrix (in linear time) to canonical form and do just one check. ------------------------ www.handcraftedgames.net

Share this post


Link to post
Share on other sites
It's integral to an implementation of dynamic narrative. I'm not at liberty to go into further detail except to say that A) planarity testing is very much a necessity and B) due to various other constraints I'm unable to utilise any of the existing well-developed graph libraries which support O(n), O(n-squared) planarity testing such as BGL, LEDA, etc. So I'm in a position where I need to develop this myself.

Share this post


Link to post
Share on other sites
Quote:
Original post by Nick of ZA
Fig.2. {v1, v4, v5} is one half of the bipartite graph, {v2, v3, v5} the other:

v 1 2 3 4 5 6
1 0 1 1 0 1 0
2 1 0 0 1 0 1
3 1 0 0 1 0 1
4 0 1 1 0 1 0
5 0 1 1 0 1 0
6 1 0 0 1 0 1


If I understand what you are saying, it would seem like there should be all zeros on the diagonal..?

Share this post


Link to post
Share on other sites
See K3,3 here -> http://en.wikipedia.org/wiki/File:Complete_bipartite_graph_K3,3.svg

If you number the top three vertices 2,3,5 and the bottom three as 1,4,6 you get the graph I'm describing in the second adj. matrix; whereas if you used 1,2,3 and 4,5,6 you'd get the former matrix. So you can see that the second adjacency matrix I've given here is correct for that case. If you're saying that if it could be converted to a diagonally-symmetrical graph, that that would open up a lot of other tools that could be applied to the matrix, I'm guessing you'd be right since that's rather a special class of matrices AFAIK. I still don't know if it would open any doors that I need opened to solve the problem of how to get a single canonical form, though.

Share this post


Link to post
Share on other sites
Correct. If you find and look at Dr. Boyer's original C++ code (it's on Google Code), you will realise that most of us will never approach the level of understanding of graphs required to competently implement the Boyer-Myrvold algorithm, or even for that matter the far more primitive Hopcroft-Tarjan algorithm which is a few decades old, and on which Boyer-Myrvold (as well as PQ-Tree and most of the others of any importance) are based.

I'm taking a roundabout route that fits my game spec, and the solution to this problem, though not critical to the overall plan I've come up with, will certainly optimise it.

So let's try to stick to the original question, which is not, "Can anyone name a planarity testing algorithm?"

[Edited by - Nick of ZA on February 23, 2010 5:59:05 PM]

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this