Planarity testing
Two functions help test if a graph is planar. The algorithm is the Boyer-Myrvold planarity tester.
K5 = clique_graph(5);
test_planar_graph(K5)
ans =
0
Of course K_5 isn't a planar graph. To get more information about why it isn't planar, we use the boyer_myrvold_planarity_test
function. When a graph isn't planar, this function will isolate a Kuratowski subgraph.
[is_planar K] = boyer_myrvold_planarity_test(K5);
is_planar
full(K)
is_planar =
0
ans =
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
A Kuratowski subgraph is a certificate that a graph isn't planar. A Kuratowski subgraph must contract to either K_5 or K_3,3
(a bipartite clique). In this case, the graph was K_5, and so K was the entire graph.
A (planar?) road network
Let's have some fun! Let's look at a road network.
load('../graphs/minnesota.mat');
gplot(A,xy,'.-');
test_planar_graph(A)
ans =
0
What? The road network isn't planar? Let's see what is going on here.
[is_planar K] = boyer_myrvold_planarity_test(A);
gplot(K,xy,'.-');
It looks like there are a lot of tree-like portions. Those shouldn't be the problem, let's remove them.
cn = core_numbers(K);
K2 = K;
K2(cn<2,cn<2) = 0;
gplot(K2,xy,'.-');
We'd better check the graph is still Kuratowski. There's a function called is_kuratowski_graph that does just this task.
is_kuratowski_graph(K2)
ans =
1
Well, that looks more helpful, but I don't see the planarity problem. Now, let's try contracting edges. What the following
code does is to look for vertices of degree 2 (pieces of a line) and remove the intermediate vertex. In Matlab it isn't very
efficent code, but this graph only has a few edges (~1000) at this point, so it'll be fast enough.
Kcur = K2;
rand('state',0);
for ntimes=1:20
d = sum(Kcur,2);
s = d==2;
s = s.*round(rand(size(s)));
a = Kcur*s;
s = s&~a;
a = Kcur*double(s);
fprintf('check for is: %i\n', full(sum(a&s))==0);
for k=find(s)'
ns = find(Kcur(:,k));
Kcur(ns(1),ns(2)) = 1;
Kcur(:,k) = 0;
Kcur(k,:) = 0;
end
Kcur = Kcur|Kcur';
end
gplot(K2,xy,'.-'); hold on; gplot(Kcur,xy,'r.-'); hold off;
check for is: 1
check for is: 1
check for is: 1
check for is: 1
check for is: 1
check for is: 1
check for is: 1
check for is: 1
check for is: 1
check for is: 1
check for is: 1
check for is: 1
check for is: 1
check for is: 1
check for is: 1
check for is: 1
check for is: 1
check for is: 1
check for is: 1
check for is: 1
Ahah, now we see the problem. (Try to untangle the red graph!)
Now that we see the problem, I think it's clear what we should have done from the beginning...
d = sum(K);
max(d)
ans =
(1,1) 3
The maximum degree is 3, so the subgraph must be isomorphic to K_3,3.
d3= d==3;
sum(d3);
That is the problem with the graph, but why doesn't the display show it? Well, it does.
gplot(K2,xy,'.-'); hold on; gplot(Kcur,xy,'r.-'); hold off;
xlim([-95.2092 -94.5842]);
ylim([ 43.5903 43.7778]);
It looks like there is a vertex of degree 4 in the middle. Unfortunately, that is just 2 paths crossing. Zooming in further,
there are actually two vertices there! That's the problem!
And so, here is a problem for you:
Problem, automatically identify the following pairs of vertices as problematic for the planar embedding [2546,2547] [1971,1975]
[1663,1666] Find another pair that prevents a planar embedding of the graph.
Planar embeddings
To investigate planar embeddings, let's start with the road network again.
load('../graphs/minnesota.mat');
test_planar_graph(A(1:500,1:500))
ans =
1
Good, we found a planar region!
A = A(1:500,1:500);
xy = xy(1:500,:);
gplot(A,xy,'.-');
Let's compute it's planar embedding
X = chrobak_payne_straight_line_drawing(A);
gplot(A,X,'.-');
Well, that isn't quite as helpful, but now you know how to compute a straight line drawing. The straight line drawing is
computed from a maximal planar graph. A maximal planar graph cannot have any additional edges and still be planar.
M = make_maximal_planar(A);
gplot(M,X,'.-');
Conclusion
That's it for our brief tour of planar graph algorithms in MatlabBGL. See the BGL documentation pages on planar graph algorithms
for more information.
Planar Graphs in the Boost Graph Library