Let $G=(\{1,\ldots,n\},E)$ be a conncected graph which is planar in the embedding where the vertices $1,\ldots,n$ are placed equidistantly on the circle and all edges are drawn as straight lines.
This graph will have one outer (unbounded) face and (potentially) a certain number of inner (compact) faces. Now iteratively remove edges separating two inner faces.
Question:
- Is this procedure well defined in the sense that it is independent of the order of removal? (I think it is)
- Is there a name for the resulting graph? I searched for "skeleton" but that does not seem to be correct. What is the structure of the resulting graph? To me it seems that all remaining inner faces will be convex polygons, and that these inner faces are interconnected by trees? Is this correct?
The procedure is well-defined (once you've chosen the embedding you start with), since you'll only be left with edges that border the external face. Those edges can never be deleted, and every other edge eventually will be.
A cactus graph is the name for the result.