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."""
Hmm, I hadn't heard of LEDA before, or these other algorithms (after finding the "most efficient" algorithm fairly quickly, I considered my search complete). Actually, though, after reading your description of their "solution" to the planarity problem, I'm not sure if I can trust them.
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
no subject
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."""
no subject