# 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?

-
Without the restriction that edges be drawn only as straight lines, these are called planar graphs; they have been well studied and are fully characterized. –  Brian M. Scott Sep 20 '12 at 21:53
Forget the straight line restriction - I assumed that that problem would be be better studied, but looks like I was wrong. –  CCC Sep 20 '12 at 22:16
Fary's theorem shows that the restriction to straight-line edges is unimportant, in the sense that every planar graph has an embedding where all the edges are straight lines. –  Rick Decker Sep 21 '12 at 1:16

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.
No, that’s Wagner’s theorem; Kuratowski’s says that a graph is planar iff it has no subgraph that is a subdivision of $K_5$ or $K_{3,3}$. –  Brian M. Scott Sep 20 '12 at 21:55