1
$\begingroup$

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?

  • 1
    [Fary's theorem](http://en.wikipedia.org/wiki/F%C3%A1ry%27s_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.2012-09-21

1 Answers 1

4

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.

  • 0
    @gt6989b But, in general, the conditions of being a subdivision of a graph, or having a minor of the same graph are not equivalent.2012-09-21