<html xmlns:mwsh="http://www.mathworks.com/namespace/mcode/v1/syntaxhighlight.dtd">
   <head>
      <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
   
      <!--
This HTML is auto-generated from an M-file.
To make changes, update the M-file and republish this document.
      -->
      <title>Planar graphs in MatlabBGL</title>
      <meta name="generator" content="MATLAB 7.5">
      <meta name="date" content="2008-10-22">
      <meta name="m-file" content="planar_graphs">
      <link rel="stylesheet" type="text/css" href="../site.css"><style>

body {
  background: white;
  color: black;
}

p.footer {
  text-align: right;
  font-size: xx-small;
  font-weight: lighter;
  font-style: italic;
  color: gray;
}

pre.codeinput {
  margin-left: 20px;
  margin-top: 10px;
  margin-bottom: 10px;
  background-color: #bbbbbb;
  border: solid 1px;
  font-size: 10pt;
  width: 620px;
}

p
{
	margin: 10px;
}

hr
{
    color: #bbbbbb;
    height: 4;
}

.main
{
	border-left-style: solid;
	margin-left: 100px;	
	width: 650px;
}

.upwhitesq
{
    position: relative;
    left: -5px;
    top: -8px;
    background: white;  
}
.downwhitesq
{
    position: relative;
    left: 95px;
    bottom: 10px;
    background: white;  
}

img
{
	text-align: center;
}

span.keyword {color: #0000FF}
span.comment {color: #228B22}
span.string {color: #A020F0}
span.untermstring {color: #B20000}
span.syscmd {color: #B28C00}

pre.showbuttons {
  margin-left: 30px;
  border: solid black 2px;
  padding: 4px;
  background: #EBEFF3;
}

pre.codeoutput {
  margin-left: 20px;
  margin-top: 10px;
  margin-bottom: 10px;
  font-size: 10pt;
  width: 520px;
}

pre.error {
  color: red;
}

.intro {
  width: 650px;
}

    </style></head>
   <body>
      <h1>Planar graphs in MatlabBGL</h1>
      <introduction>
         <div class="intro">
            <p>In version 1.35.0, the Boost Graph Library added a large suite of planar graph algorithms.</p>
         </div>
      </introduction>
      <h2>Contents</h2>
      <div>
         <ul>
            <li><a href="#1">Planarity testing</a></li>
            <li><a href="#4">A (planar?) road network</a></li>
            <li><a href="#14">Planar embeddings</a></li>
            <li><a href="#18">Conclusion</a></li>
         </ul>
      </div>
      <div class="main">
         <h2>Planarity testing<a name="1"></a></h2>
         <p>Two functions help test if a graph is planar.  The algorithm is the Boyer-Myrvold planarity tester.</p><pre class="codeinput">K5 = clique_graph(5);
test_planar_graph(K5)
</pre><pre class="codeoutput">
ans =

     0

</pre><p>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.
         </p><pre class="codeinput">[is_planar K] = boyer_myrvold_planarity_test(K5);
is_planar
full(K)
</pre><pre class="codeoutput">
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

</pre><p>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.
         </p>
         <hr>
         <div class="upwhitesq">&nbsp;</div>
         <h2>A (planar?) road network<a name="4"></a></h2>
         <p>Let's have some fun!  Let's look at a road network.</p><pre class="codeinput">load(<span class="string">'../graphs/minnesota.mat'</span>);
gplot(A,xy,<span class="string">'.-'</span>);
</pre><img vspace="5" hspace="5" src="planar_graphs_01.png"> <pre class="codeinput">test_planar_graph(A)
</pre><pre class="codeoutput">
ans =

     0

</pre><p>What?  The road network isn't planar?  Let's see what is going on here.</p><pre class="codeinput">[is_planar K] = boyer_myrvold_planarity_test(A);

gplot(K,xy,<span class="string">'.-'</span>);
</pre><img vspace="5" hspace="5" src="planar_graphs_02.png"> <p>It looks like there are a lot of tree-like portions.  Those shouldn't be the problem, let's remove them.</p><pre class="codeinput">cn = core_numbers(K);
K2 = K;
K2(cn&lt;2,cn&lt;2) = 0;
gplot(K2,xy,<span class="string">'.-'</span>);
</pre><img vspace="5" hspace="5" src="planar_graphs_03.png"> <p>We'd better check the graph is still Kuratowski.  There's a function called is_kuratowski_graph that does just this task.</p><pre class="codeinput">is_kuratowski_graph(K2)
</pre><pre class="codeoutput">
ans =

     1

</pre><p>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.
         </p><pre class="codeinput">Kcur = K2;

rand(<span class="string">'state'</span>,0); <span class="comment">% reset for deterministic results</span>
<span class="keyword">for</span> ntimes=1:20
    <span class="comment">% compute the degree of all edges</span>
    d = sum(Kcur,2);
    <span class="comment">% pick an independent set of vertices with degree 2</span>
    s = d==2;
    s = s.*round(rand(size(s))); <span class="comment">% randomly pick entries</span>
    a = Kcur*s; <span class="comment">% follow one edge</span>
    s = s&amp;~a; <span class="comment">% remove dependent edges</span>
    a = Kcur*double(s);
    fprintf(<span class="string">'check for is: %i\n'</span>, full(sum(a&amp;s))==0); <span class="comment">% verify indep set.</span>

    <span class="comment">% contract the edges</span>
    <span class="keyword">for</span> k=find(s)'
        ns = find(Kcur(:,k));
        Kcur(ns(1),ns(2)) = 1;
        Kcur(:,k) = 0;
        Kcur(k,:) = 0;
    <span class="keyword">end</span>
    Kcur = Kcur|Kcur';
<span class="keyword">end</span>

<span class="comment">% plot the graph after contraction in red</span>
gplot(K2,xy,<span class="string">'.-'</span>); hold <span class="string">on</span>; gplot(Kcur,xy,<span class="string">'r.-'</span>); hold <span class="string">off</span>;
</pre><pre class="codeoutput">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
</pre><img vspace="5" hspace="5" src="planar_graphs_04.png"> <p>Ahah, now we see the problem.  (Try to untangle the red graph!)</p>
         <p>Now that we see the problem, I think it's clear what we should have done from the beginning...</p><pre class="codeinput">d = sum(K);
max(d)
</pre><pre class="codeoutput">
ans =

   (1,1)        3

</pre><p>The maximum degree is 3, so the subgraph must be isomorphic to K_3,3.</p><pre class="codeinput">d3= d==3;
sum(d3);
</pre><p>That is the problem with the graph, but why doesn't the display show it? Well, it does.</p><pre class="codeinput">gplot(K2,xy,<span class="string">'.-'</span>); hold <span class="string">on</span>; gplot(Kcur,xy,<span class="string">'r.-'</span>); hold <span class="string">off</span>;
xlim([-95.2092  -94.5842]);
ylim([   43.5903   43.7778]);
</pre><img vspace="5" hspace="5" src="planar_graphs_05.png"> <p>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!
         </p>
         <p>And so, here is a problem for you:</p>
         <p>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.
         </p>
         <hr>
         <div class="upwhitesq">&nbsp;</div>
         <h2>Planar embeddings<a name="14"></a></h2>
         <p>To investigate planar embeddings, let's start with the road network again.</p><pre class="codeinput">load(<span class="string">'../graphs/minnesota.mat'</span>);
test_planar_graph(A(1:500,1:500))
</pre><pre class="codeoutput">
ans =

     1

</pre><p>Good, we found a planar region!</p><pre class="codeinput">A = A(1:500,1:500);
xy = xy(1:500,:);

gplot(A,xy,<span class="string">'.-'</span>);
</pre><img vspace="5" hspace="5" src="planar_graphs_06.png"> <p>Let's compute it's planar embedding</p><pre class="codeinput">X = chrobak_payne_straight_line_drawing(A);
gplot(A,X,<span class="string">'.-'</span>);
</pre><img vspace="5" hspace="5" src="planar_graphs_07.png"> <p>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.
         </p><pre class="codeinput">M = make_maximal_planar(A);
gplot(M,X,<span class="string">'.-'</span>);
</pre><img vspace="5" hspace="5" src="planar_graphs_08.png"> <hr>
         <div class="upwhitesq">&nbsp;</div>
         <h2>Conclusion<a name="18"></a></h2>
         <p>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.
         </p>
         <p><a href="http://www.boost.org/doc/libs/1_36_0/libs/graph/doc/planar_graphs.html"> Planar Graphs in the Boost Graph Library</a></p>
         <hr>
         <div class="upwhitesq">&nbsp;</div>
      </div>
      <div class="downwhitesq">&nbsp;</div>
      <!--
##### SOURCE BEGIN #####
%% 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>



##### SOURCE END #####
-->
   </body>
</html>