2
$\begingroup$

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?
$\endgroup$
3
  • 2
    $\begingroup$ Could you draw an example? $\endgroup$ Jan 28, 2021 at 20:12
  • 1
    $\begingroup$ I suspect these graphs are equivalent to what's known as outerplanar graphs (i.e., graphs in which every vertex touches the outer face), so that may be a useful definition to look at. All these graphs are certainly outerplanar, and I think you can represent every outerplanar graph like this, but I'm less sure of that. $\endgroup$ Jan 28, 2021 at 22:55
  • $\begingroup$ I will add an example tomorrow. Thanks for the reference to outerplanar graphs. That’s almost what I am looking for, except that I would like to impose the stricter condition that every edge is adjacent to the outer face. However, „edge-outerplanar“ does not seem to be a commonly used key word. $\endgroup$
    – Julian
    Jan 28, 2021 at 23:48

1 Answer 1

3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.