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.