PlanarQ

As of Version 10, most of the functionality of the Combinatorica package is built into the Wolfram System. >>

PlanarQ[g]
yields True if graph is planar, meaning it can be drawn in the plane so no two edges cross.

DetailsDetails