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?

  • 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 Apr 28 at 8:49
  • $\begingroup$ @FedorPetrov The algorithm here chooses a specific first cycle, as far as I can tell. I have not been able to find such remarks. $\endgroup$ – user139952 Apr 28 at 14:17

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$.


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.