Here's a Numberphile video that talks about embedding graphs. I think this happens because the subset of graphs that are able to be embedded in a plane is actually fairly limited.

https://www.youtube.com/watch?v=xBkTIp6ajAg