3
$\begingroup$

It is known that a graph is 2-vertex-connected iff it has an (open) ear decomposition, and there is a linear-time algorithm for finding an ear decomposition.

I think it is also true that if a graph is 2-vertex-connected, we can find an ear decomposition starting with any arbitrary cycle as the first ear. Also, there should still be a linear-time algorithm for finding such an ear decomposition. However, I cannot find any reference for this. Is it stated somewhere?

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ Does the proof (and algorithm) which you know really depend on the first cycle? For natural algorithms they seem to not depend at all, and in the books it may probably be observed in remarks. $\endgroup$
    – Fedor Petrov
    Commented Apr 28, 2019 at 8:49

1 Answer 1

Reset to default
1
$\begingroup$

The paper of Schmidt that you found answers the question in the positive, both existence and algorithm. Start the DFS on $C$ and preferentially follow edges of $C$ until the final edge, which becomes a back-edge to the root. Then in the second stage you can choose $C_1=C$.

Improve this answer
$\endgroup$

You must log in to answer this question.

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