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?

  • 1
    $\begingroup$ 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. $\endgroup$ – Brian M. Scott Sep 20 '12 at 21:53
  • $\begingroup$ Forget the straight line restriction - I assumed that that problem would be be better studied, but looks like I was wrong. $\endgroup$ – CCC Sep 20 '12 at 22:16
  • 1
    $\begingroup$ 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. $\endgroup$ – 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.

  • 4
    $\begingroup$ 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}$. $\endgroup$ – Brian M. Scott Sep 20 '12 at 21:55
  • 1
    $\begingroup$ @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. $\endgroup$ – gt6989b Sep 20 '12 at 22:02
  • 2
    $\begingroup$ @gt6989b Doesn't make it right. Graphs and Digraphs by Chartrand, Lesniak, and Zhang lists both theorems with the names as Brian Scott says. $\endgroup$ – Graphth Sep 20 '12 at 22:15
  • $\begingroup$ @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. $\endgroup$ – gt6989b Sep 20 '12 at 22:18
  • $\begingroup$ 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. $\endgroup$ – Patrick Da Silva Sep 20 '12 at 22:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.