3 ms·

I'd go with Tarjan and Hopcroft's planarity testing algorithm, whose runtime is linear in the number of vertices.