0:19

So as we saw before we're going to represent data items as nodes and

Â edges between nodes will represent relationships between those data items.

Â In some cases we'll have a graph, a planar graph for example.

Â A planar graph can be drawn such that the edges connecting the nodes don't cross.

Â That's called a planar embedding.

Â The same planar graph,

Â in this case you've got the same foreign nodes connected by the same five edges.

Â In this non planar embedding the edges cross.

Â And so, the same graph, they're both planar graphs.

Â What we'd like to do is be able to find the embedding,

Â the way to lay out the nodes so that the edges don't cross, so

Â it'll be clearer to the observer, the relationship between the nodes.

Â 1:05

So we can do this.

Â We can do this for very large graphs.

Â For example, here's a triangle mesh representing a geometric object.

Â It's a triangle mesh, so the vertices are nodes and

Â the edges of the triangles form the edges between the nodes.

Â This graph, this large graph of 50,000 nodes is not a planar graph,

Â but if I make cuts in it, if I separate the faces and duplicate edges,

Â I can turn it into a planar graph just by making these cuts along the black lines.

Â And as a planar graph, I can then find a way of embedding it into the plane so

Â that the edges don't cross.

Â There's so many nodes and so many edges in this this graph and

Â it's hard to see all of the edges, so trust me that they don't cross.

Â Hopefully you'll be working with fewer nodes and edges so

Â that your layouts will be a little more clear than this.

Â So there's a way we can find these embeddings automatically, and

Â it's called Tutte's Method, and it starts by picking some of your nodes and

Â defining where they should be in the layout.

Â So in this case, I'm going to use eight nodes, 12 edges that make a cube,

Â and I'm going to take these first four nodes,

Â and I'm going to find positions for them in for example an SVG Canvass.

Â I'm going to position node 1 at (0,0), node 2 at (1,0),

Â node 3 at (0,1), and node 4 at node (1,1).

Â And then I'm going to try to figure out where do I want to position nodes 5, 6, 7,

Â and 8, in order to make a plainer embedding of this graph.

Â This graph is shown in a non planar embedding,

Â because we've got edge crossings.

Â We want to find out how to make a planar embedding of it.

Â 2:49

So in order to do this automatically for any graph,

Â we're going to need to solve a linear system.

Â So we'll create a matrix.

Â In fact, an adjacency matrix,

Â a special kind of adjacency matrix called a Laplacian matrix.

Â So it's an adjacency matrix which means,

Â I'm going to take one node to another node in case of node 1 is connected to node 2,

Â so in row one, column two, I'm going to have a non zero entry.

Â In this case, the non zero entry is going to be 1 over the degree.

Â The node one has degree three,

Â it has three edges extending from it, so I'll put a one-third there.

Â And so node 1 is connected to nodes 2, 3, and 5,

Â and so I'll put one-third in columns two, three, and

Â five, and node one isn't connected to the other nodes.

Â So in those columns including node one, in those columns I'll put a zero.

Â The nice thing about the Laplacian form of an adjacency

Â matrix is the for node 1 I'm connected to three items.

Â My degree is three.

Â 4:19

First thing I'm going to do is I'm going to take that Laplace matrix, and

Â I'm going to zero out all of the rows for the nodes I've already assigned.

Â So I've already assigned Node 1, 2, 3, and 4 a position.

Â So I'll just zero those out in my adjacency matrix,

Â subtract the whole thing from the identity matrix.

Â The identity matrix just has ones down the diagonal and zeros everyplace else.

Â 4:44

That will give me this matrix A that I'm going to solve

Â in order to find the placements for nodes 5, 6, 7, and 8.

Â So I need to set up a linear system, and so

Â we'll set up a linear system for the x coordinates of our nodes, and

Â then we'll set up a separate linear system for the y coordinates.

Â So the linear system we use for the x coordinates looks like this.

Â It's my matrix A, and then I've got times x,

Â a column vector that's just the x coordinates of my nodes, and

Â then finally I've got the answer, what the x coordinates actually should be in

Â the case of the first four nodes and then zeros for the nodes I want to solve.

Â So this is saying that one times x one, the x coordinate of node one,

Â one time x one and zero times everything else equals zero.

Â Because that what I've assigned.

Â So here I've got node 0, node 1, nodes 2 and node 3,

Â these are the x coordinates of node 1, 2, 3, and 4.

Â And so here I've got one, this second row.

Â 1 times x2 is equal to 1, and the x coordinate of a sine for node two is one.

Â So that's what I put in these first entries

Â of this bx column vector, and the remaining entries are just zero.

Â The nice thing here is that if we look at row five,

Â row five says that the x coordinate of node 5, x5,

Â one times x5 minus one-third times x1,

Â minus one-third times x6,

Â minus one-third times x7, is going to be equal to zero.

Â 6:34

That's basically setting up a linear equation so

Â that wherever I position nodes 6 and 7, they're going to impact node 5.

Â Once we do that for rows five, six, seven, and eight corresponding to nodes 5,

Â 6, 7, and 8, and when we solve this system we'll have positions for

Â nodes 5, 6, 7, and 8 that solve that relationship.

Â 7:00

Do the same thing for the y coordinates.

Â So now my by column vector is equal to the y coordinates for nodes 1, 2,

Â 3 and 4 that I've placed, and then add zeroes for everything else.

Â Node 1 has zero for the y coordinate.

Â Node 2 has zero for the y coordinate.

Â Node 3 has one for the y coordinate, and node 4 has one for the y coordinate,

Â and this is basically saying that y1 = 0, y2 = 0, y3 = 1, y4 = 1.

Â But it's saying that the y coordinate for

Â node 5 is equal to whatever the y coordinate is for node 5, minus one-third,

Â times the y coordinate for node 1, minus one-third the y coordinate for node 6,

Â and minus one-third the y coordinate for node 7, and so on for the remaining nodes.

Â 7:52

So I've basically setup these equations for the x system.

Â I said x1 is equal to zero, x2 is equal to one, x3 is equal to zero, and

Â x4 is equal to one.

Â And then I've set up these equations for the x coordinates of the remaining.

Â I've set up similar equations for the y coordinate.

Â 8:14

So if I group these together, I basically position x1 and

Â y1 at the xy coordinates for node 1 at (0, 0), node 2 at (1,

Â 0), node 3 at (0, 1), node 4 at (1, 1), and

Â I've set up these relationships for remaining coordinates.

Â Now, you might notice something here.

Â I'm basically saying that node 5 It's going to be node 1's position

Â plus node 6 position plus node 7 position divided by three.

Â So basically the position of each node is going to be the average of the position

Â of its neighboring nodes that it shares an edge with, and that's true for

Â all the remaining nodes.

Â And so we fix the position, we set the position for

Â some of our nodes and then the remaining are just

Â going to be set to be the average of the nodes that are connected to.

Â 9:12

And so if I solve that system, if I solve that linear system you can use any

Â numerical methods you like to solve that matrix problem, you get the solution.

Â So that node 5 is at (1/3, 1/3).

Â Node 6 is at (2/3, 1/3).

Â Node 7 is at (1/3, 2/3), and node 8 is at (2/3, 2/3).

Â And so each of these nodes ends up being at the average, the position of node five

Â is equal to the average, the centroid of node one, node six, and node seven.

Â So I take node 1 plus the position of node 6 plus the position of node 7,

Â divide by three, and I get node 5.

Â 9:52

So we've solved for these positions of node 5, 6, 7, and

Â 8 to find this planar layout of this graph shown here in a non planar

Â embedding by solving a matrix problem.

Â You don't have to solve a matrix necessarily to do this.

Â You can do the same thing by basically starting with your nodes 1, 2,

Â 3, 4 in their fixed position, and then for all the remaining nodes,

Â you can assign them random positions to begin with and then iteratively,

Â replace those node positions with the average of their neighboring nodes.

Â And if you continually replace every node's position

Â with the average of it's neighboring node's position,

Â those nodes'll work into place where they belong.

Â And so you can solve this system without setting up a matrix

Â just by constantly doing that iterative procedure

Â of moving every node to the average of it's neighboring nodes.

Â 10:52

So Tutte's method tells us that we can solve a linear system to embed a planar

Â graph, but it's not that difficult.

Â You can do the exact same thing by nailing down

Â a few of your nodes into fixed positions.

Â And then the rest of the nodes,

Â you just replace their position with average of their neighbor's positions,

Â the positions of the neighbors that share an edge with that node.

Â If you keep doing that over and over, those nodes will relax into the exact same

Â position that tutte's method will converge to.

Â [MUSIC]

Â