I have K vertices and I need to connect them to form a graph. I am currently generating a complete undirected graph that looks like these:
However, I only need the exterior edges, the edges that would make up the perimeter. That would be the red edges below. Any other edges on the inside I can remove.
I'm searching for an algorithm that will help me generate just the outside edges, or an algorithm that will let me detect the outside edges so that I can remove them. I've looked into things like edge coloring, edge contraction, and even generating cycle graphs, but none of them seem to do what I want. I think part of the issue is my lack of terminology so searching isn't giving me great results.
Is there an algorithm given K vertices that I can form a graph of just the exterior edges?
This is a geometric problem. You have a finite set of points $S\subseteq \mathbb R^n$, and you want to determine the edges which bound the convex hull of $S$ (since this is a polytope).
First, you need to determine which of the points in $S$ are actually vertices on the boundary—there are many algorithms to do this, known as convex hull algorithms, such as Quickhull.
Once you have the set $B\subseteq S$ of boundary points of the convex hull, you can find the edges by considering each pair of points $P,Q\in B$ (there are $\binom{|B|}2$ such pairs) and use linear programming to check whether the midpoint $(P+Q)/2$ is in the convex hull of the $|B|-2$ remaining points.
This is more of a geometry thing rather than a graph theory thing. In graph theory we usually don't care about the position of the points.