# Find border edges of the graph

4 views (last 30 days)
NA on 12 May 2020
Commented: Christine Tobler on 14 May 2020
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]

Christine Tobler on 12 May 2020
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.
NA on 13 May 2020
Do you want the border to be defined such that all vertices except 2 and 3 are part of it?
yes. I want this border (1,8), (8,7), (7,6), (6,1), (1,5), (5,4), (4,1)
Christine Tobler on 14 May 2020
Okay, so the problem that I'm not sure how to define this in general. We could say that each simple cycle in the graph represents a polygon, and a vertex is not on the border only if it's inside one or more of these polygons. Here a simple cycle is a list of nodes where each consecutive pair is connected by an edge, with no repeating nodes and where the last node connects back to the first.
But it's possible to have a cycle which does not form a simple polygon, because the lines intersect. Here's an example of that:
Is there something about the data you're looking at that makes sure this couldn't happen? Or if not, how would you want to treat this case?
You might have a look at the polyshape class, which feels like it could be more relevant to the kind of data you're working with.