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.)
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?