%% Planar graphs in MatlabBGL
% In version 1.35.0, the Boost Graph Library added a large suite of planar
% graph algorithms.
%% 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)
%%
% 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)
%%
% 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)
%%
% 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)
%%
% 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); % reset for deterministic results
for ntimes=1:20
% compute the degree of all edges
d = sum(Kcur,2);
% pick an independent set of vertices with degree 2
s = d==2;
s = s.*round(rand(size(s))); % randomly pick entries
a = Kcur*s; % follow one edge
s = s&~a; % remove dependent edges
a = Kcur*double(s);
fprintf('check for is: %i\n', full(sum(a&s))==0); % verify indep set.
% contract the edges
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
% plot the graph after contraction in red
gplot(K2,xy,'.-'); hold on; gplot(Kcur,xy,'r.-'); hold off;
%%
% 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)
%%
% 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))
%%
% 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.
%
% <http://www.boost.org/doc/libs/1_36_0/libs/graph/doc/planar_graphs.html
% Planar Graphs in the Boost Graph Library>