
タイトル：
Planar Graphs  Intro to Algorithms

概説：

Another category of graphs that are very important and come up a lot are planar graphs.

These are graphs that can be drawn in the plane on a flat piece of paper

so that the edges don't cross.

Here's an example of a planar graph.

We've got five nodes and five edges.

You see the way I drew it here. This node here and this node needed to be connected.

I just drew a nice, little curvy line without crossing anything else.

This is a planar graph. It still would be a planar graph even if I drew it with a crossing in it,

because the issue is that there is some way to do it so that the edges don't cross.

Now, in this particular example, we've got five nodes and five edges,

but what we're interested in is what is the relationship in general between the number

of nodes in a planar graph and the number of edges.

This is more complicated example than any of the ones we looked at before in this unit.

There is some kind of a relationship, and there are constraints

by virtue of the fact that the graph is drawn in the plane.

Let's take a look at that. Let's think about adding some edges here.

We can add that edge. We can add this edge. We can add this edge.

We can add this edge, and are there any more edges we can add

while still being able to draw it in a plane? It doesn't look that way, right?

This node is connected to all the other nodes. This one is done.

This node is connected to three other nodes, but it can't reach this one.

It seems like it's sort of all blocked out. That's going to be true in general.

There's going to be some graphs that can't be drawn as a planar graph.

If we add this edge between this node and this node, the resulting graph is no longer planar.

How many edges do we get here all told?

We've got one, two, three, four, five, six, seven, eight, nine.

In this example, the number of edges seems to need to be less than or equal to 9.