Linear time, to be precise. But, as you say, complicated -- the LEDA folks at least initially decided to write up two planarity tests and if they gave different answers, use a much more expensive but simple algorithm.

Time n^(3/2) is easy using springs (each edge is a spring, then you solve the system using conjugate gradiant). Newer linear solvers run in O(n log n) time """in practice."""