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.
Algorithms that locate a Kuratowski subgraph in linear time in vertices were developed by Williamson in the 1980s.
While this is conceptually very simple (and gives linear running time), the method itself suffers from the complexity of finding the construction sequence.