This is a well-studied problem in computer science for which many practical algorithms have emerged, many taking advantage of novel data structures.
[2][3][4] In 2012, Taylor[5] extended this algorithm to generate all permutations of cyclic edge-order for planar embeddings of biconnected components.
[6] It was improved by Even and Tarjan, who found a linear-time solution for the s,t-numbering step,[7] and by Booth and Lueker, who developed the PQ tree data structure.
Furthermore, the Boyer–Myrvold test was extended to extract multiple Kuratowski subdivisions of a non-planar input graph in a running time linearly dependent on the output size.
[15] The source code for the planarity test[16][17] and the extraction of multiple Kuratowski subdivisions[16] is publicly available.
While this is conceptually very simple (and gives linear running time), the method itself suffers from the complexity of finding the construction sequence.