Recently I learnt that for any graph, being 2-connected is a necessary condition for the existence of a ear decomposition. For a planar graph, if it is 2-connected, will its dual also be 2-connected (i.e. having a ear decomposition)?

Given its ear decomposition, based on that I believe that the dual graph will also have a ear decomposition.

Below shows some examples I have found and they can tell how the dual can if I add one more path to the existing ear decomposition. The one on the bottom left is the original graph with a ear decomposition and its dual. By induction on the number of paths which will be added, I can find 3 possibilities of what the dual will be.

enter image description here

In the example on the bottom right, I add the new path, $P_3$ inside the cycle in the centre to split it. On the bottom left, I add the $P_3$ so that $P_3$ does not "contain" any cycles and on the bottom right, I add $P_3$ such that it will "contain" a existing cycle (or it could contain more but I would like to focus on this case first).

Although I believe that, I have difficulties describing all possibilities after I add a new path to the current 2-connected graph. If you have some ideas of how to summarize all the possibilities in a rigorous way, please feel free to leave any comments.

The definition of "ear decomposition" and "2-connected" are included in the following link: https://en.wikipedia.org/wiki/Ear_decomposition


Your Answer

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

Browse other questions tagged or ask your own question.