I transformed the really bad case into a rectangular map to play with the Java program and Kempe random switches.
Here is the graph with the two edges to connect:
The two edges marked with the X, have to be joined by a new edge that form a new F5 face.
To try the Java program, rebuild this graph and play with the switches, it is possible to use this string:
- 1b+, 2b+, 3b+, 4b+, 5b+, 15b+, 14b-, 13b-, 5e-, 6b-, 12b-, 4e-, 8b-, 13e-, 6e-, 9b-, 12e-, 11b-, 3e-, 14e-, 10b-, 7b-, 2e-, 8e-, 9e-, 11e-, 7e-, 10e-, 15e+, 1e+
Next is the graph that shows how the graph has been converted: