# How to obtain the list of outermost graph nodes

For the following image:

The attached code produces a graph.

img = Import["https://i.sstatic.net/Yj6npagx.png"]
g = img // ColorNegate // Binarize //
MorphologicalGraph[#, VertexLabels -> "Name"] &


How do I obtain the list of outermost nodes as follows?

{1, 2, 7, 12, 14, 13, 4}


img = Import["https://i.sstatic.net/Yj6npagx.png"]
g = img // ColorNegate // Binarize //
MorphologicalGraph[#, VertexLabels -> "Name"] &


ge = GraphEmbedding[g];
pts = ConvexHullMesh[ge] // MeshCoordinates;
fst = FindShortestTour[pts];
outermost = Lookup[lut, pts[[Most@Last@fst]]];


{1, 2, 7, 12, 14, 13, 4}

HighlightGraph[g, outermost, VertexSize -> Large
]


Clear["Global*"];
im = Import["https://i.sstatic.net/Yj6npagx.png"];
g0 = MorphologicalGraph[Binarize@ColorNegate@im,
VertexLabels -> Automatic];
coords = GraphEmbedding[g0];
g = AdjacencyGraph[coords, m, VertexCoordinates -> coords];
reg = ConvexHullMesh[coords];
pts = MeshPrimitives[RegionBoundary@ConvexHullMesh[coords], 1][[;; ,
1]][[;; , 1]];
indexs = VertexList[g0][[Flatten[Position[coords, #] & /@ pts]]];
{HighlightGraph[g, pts, VertexSize -> .2, VertexLabels -> Automatic],
HighlightGraph[g0, indexs, VertexSize -> .2,
VertexLabels -> Automatic]}
indexs


{1, 2, 7, 12, 14, 13, 4}.

Since you did not really specify what you mean by the "outermost graph nodes", and the approaches by @Syed and @cvgmt only work for convex graphs, here is an approach that works also for non-convex graphs, and where the "outermost graph nodes" are defined as the nodes of the "outer face". The key function used is PlanarFaceList.

pts = AssociationThread[VertexList[g] -> GraphEmbedding[g]];
outer = Select[PlanarFaceList[g],
And @@ (RegionMember[Polygon[Values@KeyTake[pts, #]]] /@ Values@pts) &]
(* {{1, 4, 13, 14, 12, 7, 2}} *)


An example of a non-convex graphs:

g = Graph[{{1, 2}, {2, 3}, {3, 1}, {3, 4}, {4, 5}, {5, 6}, {6, 4}}]
HighlightGraph[g, outer]


• Before I post my answer, I also test the graph g = HypercubeGraph[3]; That is why I use ConvexHullMesh`. Commented Apr 29 at 10:48
• @cvgmt, well, I somehow assumed that the input graph should be in a planar embedding ... But mainly I just wanted to emphasize that the initial problem posed by the OP is not really well-defined. Commented Apr 29 at 11:00