2
$\begingroup$

Let $T$ be a given (finite) tree.

Question 1: Is it always possible to add edges to $T$ to obtain a $2$-connected outerplanar supergraph $G$?

Question 2: If the answer to Question #1 is negative, can the trees for which it is possible be characterized?

Question 3( Defect form of Question 1): Let $T$ be a rooted tree with root vertex $v_{0} \in V(T)$. Is it always possible to add edges to $T$ to obtain a $2$-connected planar graph $G$ with a plane embedding in which $v_{0}$ is the only internal vertex?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Any tree is already outerplanar, right? $\endgroup$
    – Sam Hopkins
    Commented Jan 31, 2022 at 15:37
  • 1
    $\begingroup$ @SamHopkins Yes, of course. I meant a 2-connected one. Many thanks for noticing the error! $\endgroup$
    – Felix Goldberg
    Commented Jan 31, 2022 at 15:38

1 Answer 1

Reset to default
2
$\begingroup$

Yes. Pick an arbitrary vertex to be the root. Consider the sequence of vertices $v_1, v_2, \ldots$ produced by a pre-order traversal of the rooted tree, adding edges $v_i - v_{i+1}$ where they don't already exist. Finally, add an edge back from the last vertex to the root, if it doesn't already exist. This cycle defines the outer face and gives 2-connectivity.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks, this is very nice! Do you know of a reference where this is discussed perhaps? $\endgroup$
    – Felix Goldberg
    Commented Feb 6, 2022 at 10:30
  • $\begingroup$ @FelixGoldberg, no, sorry. I'm sure it's not original, but I came up with it independently. $\endgroup$
    – Peter Taylor
    Commented Feb 6, 2022 at 13:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .