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
    Without the restriction that edges be drawn only as straight lines, these are called [*planar graphs*](http://en.wikipedia.org/wiki/Planar_graph); they have been well studied and are fully characterized.2012-09-20
  • 0
    Forget the straight line restriction - I assumed that that problem would be be better studied, but looks like I was wrong.2012-09-20
  • 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.

  • 4
    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}$.2012-09-20
  • 1
    @BrianM.Scott R. Diestel in 2nd edition of his "Graph Theory" lists both Kuratowski 1930 and Wagner 1937 as sources for Theorem 4.4.6, which states that graphs are plananr iff they have no K5/K33 minors and equivalently if they don't have K5/K33 topological minors. He refers to it as Kuratowski's theorem.2012-09-20
  • 2
    @gt6989b Doesn't make it right. Graphs and Digraphs by Chartrand, Lesniak, and Zhang lists both theorems with the names as Brian Scott says.2012-09-20
  • 0
    @Graphth I don't have a strong opinion, and am perfectly happy to edit the answer. I just thought that since Diestel is a very respectable reference, it may be some argument in the academic community in whose name to call this result. If you think changing the answer to make it Wagner's theorem is appropriate, I will do that.2012-09-20
  • 0
    To be honest I had never heard of Wagner's before, always thought the theorem was attributed to Kuratowski and no one else, I am learning something right now. I tried looking for references by googling "Planar graph" and I keep falling on Kuratowski's name, Wagner's barely appeared.2012-09-20
  • 0
    @PatrickDaSilva I think the link to wiki in the answer lists them both... But I guess you are right, it depends on which books you read. It was a new thing for me as well...2012-09-20
  • 0
    If graph $A$ is a subdivision of graph $B$, then graph $B$ is a minor of graph $A$, but not vice versa. So, Wagner's theorem and Kuratowski's theorems are different, with Wagner's being stronger. I believe that some books people use the terms minor/topological minor as opposed to subdivision/minor. Am I right, or am I right? In that case, what you state as Kuratowski's theorem could actually be his, but using minor=subdivision.2012-09-21
  • 0
    @Graphth Could be, haven't heard of subdivisions before. Either way, Diestel proves that absence of either $K_5/K_{3,3}$ minor, or absence of $K_5/K_{3,3}$ topological minor both characterize planar graphs (i.e. they are equivalent conditions).2012-09-21
  • 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