Find border edges of the graph

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]

Answer 1

[Christine Tobler]

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]

Why vertex 1 does not participate in the border?

[Christine Tobler]

Vertex 1 is located in the center of the points, I had assumed you wanted the border to contain the vertices on the outside of the region defined by the set of vertices.

Do you want the border to be defined such that all vertices except 2 and 3 are part of it?

[NA]

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]

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.