What set of graphs can be drawn on a plane such that no edges intersect? It's seems like all acyclic graphs can, but not all cyclic graphs (I.e. The fully connected 4 node graph can, but the fully connected 5 node graph cannot)
Also, is there a name for this property?
(Don't know if it makes a difference, but if it does, let's assume edges can only be drawn as straight lines and that nodes are drawn as points, not shapes w/ an area.)
Edit:
Follow up question: While Wikipedia has taught me that planarity testing can be done in a computationally efficient manner, I wonder about a related problem: given a non-planar graph, is it possible to determine the smallest number edges that must be removed to create a planar graph in some manner that's more efficient than simple brute force?

Planar graphs are those which have a $\mathbb{R}^2$ embedding without edge crossings. Kuratowski's Theorem states that a graph is planar if and only if it has no $K_5$ or $K_{3,3}$ minor.
