MATLAB: Find border edges of the graph

find border edges of the graphgraph theory

I have a graph like this, how I can find border edges.
M = [1 8; 7 8; 1 7; 7 6; 1 6; 1 5; 4 5; 1 3; 2 3; 1 2; 1 4];
Layout = [3 2; 5 2; 5 4; 6 1; 6 6; 4 6; 2 4; 1 1];
g = graph(M(:, 1), M(:, 2));
h = plot(g);
h.XData=Layout(:,1);
h.YData=Layout(:,2);
The border edges in this graph is (1,8), (8,7), (7,6), (6,1), (1,5), (5,4), (4,1)
result should be:
border_edges = [1,8; 8,7; 7,6; 6,1; 1,5; 5,4; 4,1]
The other question is that, how I can find nodes with 2 edges?
node_with_two_edges =[8; 6; 5; 4; 2; 3]

Best Answer

The graph class doesn't have any functions based on coordinates of the points - it just knows about their connections. Use convex hull to find the nodes that lie on the border:
>> K = convhull(Layout(:, 1), Layout(:, 2));
>> plot(Layout(:, 1), Layout(:, 2), 'x'); hold on; plot(Layout(K, 1), Layout(K, 2), 'o-')
For finding all nodes with 2 edges, use degree(g) == 2.
Related Question