No BSD License  

Highlights from



David Gleich (view profile)


30 Apr 2006 (Updated )

MatlabBGL provides robust and efficient graph algorithms for Matlab using native data structures.

%% 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);

% 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);

% 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.


% What?  The road network isn't planar?  Let's see what is going on here.
[is_planar K] = boyer_myrvold_planarity_test(A);


% 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;

% We'd better check the graph is still Kuratowski.  There's a function
% called is_kuratowski_graph that does just this task.


% 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;
    Kcur = Kcur|Kcur';

% 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);

% The maximum degree is 3, so the subgraph must be isomorphic to K_3,3.
d3= d==3;

% 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.

% Good, we found a planar region!
A = A(1:500,1:500);
xy = xy(1:500,:);


% Let's compute it's planar embedding
X = chrobak_payne_straight_line_drawing(A);

% 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);

%% 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>

Contact us