## ← Planar Graphs - Intro to Algorithms

• 2 フォロワーs
• 27 Lines

### 埋め込みコードを取得する x Embed video Use the following code to embed this video. See our usage guide for more details on embedding. Paste this in your document somewhere (closest to the closing body tag is preferable): ```<script type="text/javascript" src='https://amara.org/embedder-iframe'></script> ``` Paste this inside your HTML body, where you want to include the widget: ```<div class="amara-embed" data-url="http://www.youtube.com/watch?v=NJ_5X-JB3A8" data-team="udacity"></div> ``` 3言語

Showing Revision 2 created 05/25/2016 by Udacity Robot.

1. Another category of graphs that are very important and come up a lot are planar graphs.
2. These are graphs that can be drawn in the plane on a flat piece of paper
3. so that the edges don't cross.
4. Here's an example of a planar graph.
5. We've got five nodes and five edges.
6. You see the way I drew it here. This node here and this node needed to be connected.
7. I just drew a nice, little curvy line without crossing anything else.
8. This is a planar graph. It still would be a planar graph even if I drew it with a crossing in it,
9. because the issue is that there is some way to do it so that the edges don't cross.
10. Now, in this particular example, we've got five nodes and five edges,
11. but what we're interested in is what is the relationship in general between the number
12. of nodes in a planar graph and the number of edges.
13. This is more complicated example than any of the ones we looked at before in this unit.
14. There is some kind of a relationship, and there are constraints
15. by virtue of the fact that the graph is drawn in the plane.
16. Let's take a look at that. Let's think about adding some edges here.