Determining if $G$ contains $K_4$ as a minor in polynomial time

I am trying to devise an algorithm for determining if an undirected graph $G$ contains $K_4$ as a minor. I was able to show in a previous problem how to test for $K_{2,3}$ by looking at all pairs of vertices and applying Menger's problem as a black-box on that pair of vertices (i.e checking for at least 3 vertex-disjoint paths). This gave an, although naive, $O(n^3)$ algorithm. However, the same trick doesn't seem to work for $K_4$, since the same type of structure cannot be exploited. How can one test for $K_4$?

I am also wondering what the best possible algorithm for $K_{2,3}$ and $K_4$ testing might be.... I seriously doubt that the brute-force approach highlighted above is optimal. Is there a known lower-bound?

I think your best bet would be to implement a treewidth 2 algorithm. We implemented one for an android app and you can find the source code of this specific implementation here: Treewidth. You can probably modify it to run in $O(n^4)$ time.

StackExchange Computer Science Q#37728, answer score: 2