Absolutely. I mean I'm pretty sure he already knows what graphs are. They talk about them on computerphile all the time. He's asking purely on behalf of the audience.
The embedding part is quite useful in circuit design and circuit analysis. A cross-over in an electrical circuit can mean a short-circuit. You can work around it by inserting pass-throughs or even little wires that act like bridges. But the best way is to just be smart with your wiring and ensure it never crosses over itself if it can be helped. Basically, math like this can help you save money in circuits.
5 лет назад+24
Or for example if you can design a tram system in a way that the tram lines connect the stations as a planar graph, then you can be sure that no tram ever needs to wait for another. That makes planning their times much easier.
Molecules are also much nicer to draw if they can be arranged as a planar graph. I actually don't know how it would be done otherwise. Usually Chemists then become lazy and just write "C60".
@@ruinenlust_ Damn auto-correct... I had written 'grafe' which was actually also incorrect, it's "graaf" (but not as in "count"), not "grafe". Sorry about that.
@@busimagen If you mean a "glyph" (sometime indeed also called "graph"), we call that "glief". While a "grapheme" is a "grafeem". So it's quite close to each other.
@@busimagen Not really, we use the term 'staafdiagram' for bar graph. Dutch is like german in their usage of pasting words together. So you should be able to guess what a 'cirkeldiagram' is :) I don't fully understand your second example of graph?
When I studied computer science I visited a course about bioinformatics and the prof kept talking about graphs like this... and after a while you noticed half the audience giving blank stares... he was really confused until I asked some of them if maybe they were thinking about the x-y kind. Turns out someone sent some biologists to the lecture and contrary to computer scientists they had never heard about THIS kind of graph -_-
High schoolers and younger students are forced to go through the whole calculus series before even being introduced to this kind of finite maths (which is relied upon heavily in computer science and other data-driven fields) and the sprawling field of mathematics, and as a result a disheartening number of students get overwhelmed and overtaken by the workload and the maddening lack of an answer to the question of "when will we use this?". With maths like this it's possible to visualize and explain real-life applications fairly easily, and I don't think you'd necessarily need to have mastered calculus to understand the basic concepts. Maybe someday we can restructure the mathematics curriculum to include elementary non-calculus courses so that students don't have to wait until they are university sophomores to at least be introduced to these important problems.
From my personal experience, I enjoyed several years of calculus way more than a few hours of graph theory. But I guess it's a matter of taste. Even though graph theory can be useful, I didn't find it as ground breaking/mind blowing as what we learnt in other fields of math.
There are a couple of reasons why graph theory doesn't get a lot of time in schools: One is that it's still a relatively recent area of mathematics, and it takes time for things to filter down to school-level - first you need enough academics to take an interest for it to start producing useful/interesting results, then you need there to be an interest in having graduates already know something about the area, and for there to be lecturers willing to teach it. That then starts getting you maths graduates who have some awareness of it. Once you have enough maths graduates familiar with graph theory (or whatever), then they can start slipping it into school syllabuses, and there should be staff available to teach it. Another is that there's not a lot of material that depends on understanding graph theory in order to learn it. In order to follow a course on complex analysis, you need to be familiar with complex numbers and with analysis, which in turn requires proficiency with algebra, and basic arithmetic, so there's a tendency to cover the material that's needed in order to progress to advanced courses rather than material that could be studied much earlier, but isn't a prerequisite for any other courses.
While I partially agree with you, I think you need to understand that all these interesting and thought provoking bits of information is just that. Bits. On top of an arguably huge mountains of boring math. Which is what made them so special in the first place. Importance of calculus is so underrated. And I don't even use calculus. My job is far removed from math. And yet wherever I look, I can see it's distinct impression. Ever wondered why youtube is so full of videos of quantum mechanics and relativity yet in-depth teachable grade videos are near impossible to find? Because it's so f***ing tedious and boring. Academics should be decided by importance, not popularity.
@@EricAtRandom programming is just math but typed. Computer science is just a kind of math. Here, I'll name three things, tell me which of the fields it belongs to: * Numbers * Functions * Variables
@@Bliss467 That's always my response to people who say they've never needed algebra after high school ... I deal with algebra every single day and I am *not* (directly, at least) a mathematician!
I am actually surprised, that over so long time of the show running, we have not encountered graph topics. Isn't it interesting? This is a whole new dimension of videos coming on this topic :)
Strictly speaking, a thumbnail is a digital image consisting of some number of pixels organized in a N x M grid. Depending on what you think the most natural way to connect the vertices is (for example, connecting each pixel to the next pixel in its row and connecting the last pixel in a row to the first pixel in the next row, or simply connecting the pixels in a lattice), I'd argue that any thumbnail is in fact a planar graph. Of course, you can go on to say that a digital image is nothing but a sequence of bits, or that a sequence of bits is nothing more than a series of voltage measurements, or that a series of voltage measurements is just a bunch of particles moving around in particular ways we've ascribed meaning to. In that case I think we've got bigger concerns than whether a graph is planar, but it certainly would provide an interesting discussion.
@@cizdramasnedalm8055 Ok, Neil deGrasse. Technically what I'm saying here are just pixels in a grid, so do interpret the following pixels- "pedantic asshole"- however you want.
@@oliverhoare6779 Hey friend, there's no need to get all upset over a simple comment. I was just being pedantic for the sake of humor. Admittedly, the humor might have not been all that amazing, but still I don't feel like I deserved that.
We need a supercut of Numberphile videos that is just a series of all the times someone references Euler. Maybe another collab with Boyinaband to turn it into something musical.
+1. As a test, it is probably more straightforward to think of the contrapositive of the theorem: If E > 2V-4 (where V>=3) and there are no triangles, then the graph is not planar.
A while ago i found a game, called "untangle" (the main story is to free a kite, that is stuck in a tree), where the player has to untangle a mesh of vertices, that no lines are intersected without being connected to a vertex at this point. There are multiple levele, where these mashes should display tangled parts of the kitestring. Actually it´s taking a scrambled graph and transform it into a planar projection.
The last graph doesn't seem so cheaty if you think about something like a subway map. Only five stations in the city center are densely connected and most stations are only along one route, but that is enough that you can't build it without expensive crossing tunnels.
learning some of the things on this channel while in a lower level us math class is absolutely phenomenal... i dont understand it all but boy do i try to.. it seems like magic how simple//complex some if these things are and you can tell how completely the person presenting understands them and its mind boggling
delightful. thank you. your videos are a gift to the world and fill me with hope knowing people like you and these academicians are out there doing what you all do. thanks again.
@@frankstevenson5013 For any (finite?) graph on a sphere, find a blank spot and "pop" the sphere. You can map the rest to a plane, with the distortion being irrelevant in a graph sense.
For every n there exists a g so that Kn is embeddable in Fg, n and g being natural numbers. Same for Fg'. As Tom Kerruish said, even the K7 is embeddable into a Torus (F1). The K8 is not. If you take three edges out of K8, that form a triangle, the graph you get is a minimal non embeddable graph for the Torus. So taking away one more edge will allow for an embedding. The Torus has alot more minimal Graphs. Not just two, like the 2-sphere or R^2.
Nitpick just so students watching this don't get lost looking at some other source: around 12:50 when it's said that V is the # of verts and E is the # of edges, this is not standard. V is the set of vertices, and E is the set of edges. |V| is then the cardinality (size) of the set V (i.e. the number of vertices) and |E| is the cardinality of the set E.
@@codecrafter151 having only just found out about this I cant be sure, but as far as I can see you only need to make sure that each individual layer contains no non planar graphs. I'd have to try finding more information about it to see how 'easy' it is though
at 14:30 a perhaps better way of saying it would be: if you pick any three vertices of a K3,3 graph at least 2 of those vertices must come from the same side and therefore have no edge connecting them
I was working on transition-metal complexes that had a non-planar graph in its base structure a couple of years ago. My former Prof. really wanted to coin the term Kuratowski-complexes for these kinds of complexes.
The theorem saying for a planar graph, E ≤ 3V-6 apparently needs clarification since while the graph K2(two vertices joined together by one edge) is planar, the equation does not hold for this graph as shown here: 1 ≤ 3(2)-6 1 ≤ 0 (Not True)
@@brunogallego7507 That's not what maths is about... People like galois also didn't find a use for group theory, years later people found huge practical potential in that
@@brunogallego7507 Graph Theory has a wide range of applications and it forms the foundation for many algorithms in computer science. Look up the 'Koenigsberg Bridge Problem'
Is there any crazy 3d version of this, where some infinite graph is not 3d embeddable but would be in 4d? It would have to be real weird, but space filling curves are a thing...
I think so - I recall seeing a K3, 3 planar embedded using a Klein bottle as it's 2d space (on some 4chan post I think). Not 100% it's actually valid but on a glance it looked like it worked.
Is there a three dimensional equivalent of this? In three dimensions, K5 would work (picture a tetrahedron with a centerpoint), but would other graphs be impossible?
Yes! Instead of embedding (drawing) your graphs on a plane you could consider drawing them on any surface! In particular, instead of a plane you could embed them into the surface of a 3D object, like a sphere (which turns out is the same as the plane) or a donut. You could also imagine embedding them IN the 3D (or n-dimensional) object instead of just on the surface, but then you can draw any finite graph. Up to certain properties, each of these surfaces have their own "list" of smallest graphs that can't be drawn on them. A very amazing theorem (called the "Graph Minors Theorem") tells us that each of these lists contain a finite number of graphs. However, for most surfaces we don't know what those graphs are (or even how big the lists are)
3:00 -- SO YEAH, this particular graph is NOT PLANAR, *BUT* the number of vertices has a numerical relationship with the number of points where multiple lines cross. So -- are some non-planar graphs fractal?
How many colours are needed to colour the map of all the countries (as recognised by a majority of UN member states right now) if external territories are coloured the same as the main country?
I really like that you clearly know what a graph is (I've been watching this channel for a while, I'm sure you've heard of graphs). But you can still ask good, basic questions, so that your guest can give their explanations. Also, is it just me or does Leonard Euler's face looks a little bit like Matt Parker's ?
Learning basic graph theory for a tutoring interview... I got a notification for this video that just happened to be released today literally the same minute I started learning about planar graphs.
I can see how planar graphs would have many practical applications. Imagine a PCB with components soldered on like capacitors, resistors, transistors, etc. Copper lanes need to connect various components but the lanes are not allowed to intersect.
Now, the K3,3 graph, I remember this. My Question is : Why only take advantage on 1 side of the plane? If you use Both sides of the plane it is solvable (via a tunnel, or on circuit boards it's called a 'via'). The bridge to terabithia..
On wikipedia for "Planarity Tests": _"Most of these methods operate in O(n) time (linear time), where n is the number of edges (or vertices) in the graph, which is asymptotically optimal."_ Really, one looks for subdivisions of those graphs (because this is the interesting property for planarity). Note in particular: _"Algorithms that locate a Kuratowski subgraph in linear time in vertices were developed by Williamson in the 1980s."_
There's a fun puzzle here: given a graph, find a planar embedding. Google for Simon Tatham's Puzzles, and the puzzle in that collection is called "untangle". The number of hours I've spent on that...
I'm having this app for years, playing many puzzles, but I rarely played untangle because it's more guessing than thinking. Do you have any tricks or so?
@@mirkoschultz9347 It's a lot more about getting things mostly roughly right and refining later, rather than growing little areas of certainty like the other puzzles. Moving nodes close to the nodes they're connected to - if all the edges to a node form a sharp little angle, moving that node is a top priority. Doing some stuff like that to just make things nicer, before even thinking about untangling, really helps.
You may be thinking of the chromatic number of the plane (which would explain the confusion). Here the plane is seen as an infinite graph, where all points at distance 1 are adjacent. This graph is not planar (it contains a subdivision of K5), but we know that it needs between 5 and 7 colours to be properly coloured. The lower bound of 5 has been proven only recently with a very large subgraph of the graph of the plane, which needs 5 colours to be properly coloured.
Brady needs more appreciation for how good he is at asking presenters the right questions to help illuminate the topic for the viewer.
If you are subscribed (and have alerts on) then that is all the appreciation I need! :)
Numberphile I did both, you deserve it!
Absolutely. I mean I'm pretty sure he already knows what graphs are. They talk about them on computerphile all the time. He's asking purely on behalf of the audience.
@@nikanj That's what makes it impressive. It's so hard to imagine not knowing what you know so that you can make sure other people learn it.
Myrmidon
Not to mention that James Grime already mentioned planar graphs in the four-colour theorem video.
The embedding part is quite useful in circuit design and circuit analysis. A cross-over in an electrical circuit can mean a short-circuit. You can work around it by inserting pass-throughs or even little wires that act like bridges. But the best way is to just be smart with your wiring and ensure it never crosses over itself if it can be helped.
Basically, math like this can help you save money in circuits.
Or for example if you can design a tram system in a way that the tram lines connect the stations as a planar graph, then you can be sure that no tram ever needs to wait for another. That makes planning their times much easier.
Also in E/R modeling in database design.
Molecules are also much nicer to draw if they can be arranged as a planar graph. I actually don't know how it would be done otherwise. Usually Chemists then become lazy and just write "C60".
Yup I've been there
@ though in the specific case of C60, it can be represented as a planar graph (its Schlegel diagram).
In Dutch we actually have 2 different words: 'grafiek' is a graph with a function plotted on it, 'graaf' is a graph with vertices & edges.
If you'd tell me, a Dutch person, that you'd like me to draw a 'graph'....
I'd draw a tombstone.
We don't have the word 'graph' in our language.
@@ruinenlust_ Damn auto-correct... I had written 'grafe' which was actually also incorrect, it's "graaf" (but not as in "count"), not "grafe". Sorry about that.
@@PeterVC :)
@@busimagen If you mean a "glyph" (sometime indeed also called "graph"), we call that "glief". While a "grapheme" is a "grafeem". So it's quite close to each other.
@@busimagen Not really, we use the term 'staafdiagram' for bar graph. Dutch is like german in their usage of pasting words together. So you should be able to guess what a 'cirkeldiagram' is :)
I don't fully understand your second example of graph?
Correction at 13:58 - remove the word "not".
Continues with "Perfect Graphs" at ruclips.net/video/C4Zr4cOVm9g/видео.html
Numberphile kul
Thank You, For The Video
Simon Tatham's Puzzle Collection has a game called "untangle" that essentially tasks you with making a graph planar
So sexy!
Cool video! BTW, is that Omega Speedmaster Moonwatch on your wrist?
When I studied computer science I visited a course about bioinformatics and the prof kept talking about graphs like this... and after a while you noticed half the audience giving blank stares... he was really confused until I asked some of them if maybe they were thinking about the x-y kind. Turns out someone sent some biologists to the lecture and contrary to computer scientists they had never heard about THIS kind of graph -_-
High schoolers and younger students are forced to go through the whole calculus series before even being introduced to this kind of finite maths (which is relied upon heavily in computer science and other data-driven fields) and the sprawling field of mathematics, and as a result a disheartening number of students get overwhelmed and overtaken by the workload and the maddening lack of an answer to the question of "when will we use this?". With maths like this it's possible to visualize and explain real-life applications fairly easily, and I don't think you'd necessarily need to have mastered calculus to understand the basic concepts. Maybe someday we can restructure the mathematics curriculum to include elementary non-calculus courses so that students don't have to wait until they are university sophomores to at least be introduced to these important problems.
Agree thoroughly. So much exciting stuff and fairly easy to explain that never gets introduced to high school students. KNOTHEORY, fun.
From my personal experience, I enjoyed several years of calculus way more than a few hours of graph theory. But I guess it's a matter of taste. Even though graph theory can be useful, I didn't find it as ground breaking/mind blowing as what we learnt in other fields of math.
There are a couple of reasons why graph theory doesn't get a lot of time in schools:
One is that it's still a relatively recent area of mathematics, and it takes time for things to filter down to school-level - first you need enough academics to take an interest for it to start producing useful/interesting results, then you need there to be an interest in having graduates already know something about the area, and for there to be lecturers willing to teach it. That then starts getting you maths graduates who have some awareness of it. Once you have enough maths graduates familiar with graph theory (or whatever), then they can start slipping it into school syllabuses, and there should be staff available to teach it.
Another is that there's not a lot of material that depends on understanding graph theory in order to learn it. In order to follow a course on complex analysis, you need to be familiar with complex numbers and with analysis, which in turn requires proficiency with algebra, and basic arithmetic, so there's a tendency to cover the material that's needed in order to progress to advanced courses rather than material that could be studied much earlier, but isn't a prerequisite for any other courses.
While I partially agree with you, I think you need to understand that all these interesting and thought provoking bits of information is just that.
Bits.
On top of an arguably huge mountains of boring math.
Which is what made them so special in the first place.
Importance of calculus is so underrated. And I don't even use calculus. My job is far removed from math. And yet wherever I look, I can see it's distinct impression.
Ever wondered why youtube is so full of videos of quantum mechanics and relativity yet in-depth teachable grade videos are near impossible to find? Because it's so f***ing tedious and boring.
Academics should be decided by importance, not popularity.
@@dr_arcula k
"Overloading of a word" found the programmer 😅
I was thinking it was a reference to chess
That's funny! I had the same thought in reverse. I thought, "Oh, was that a mathematical term that programming languages adopted?"
@@EricAtRandom programming is just math but typed. Computer science is just a kind of math. Here, I'll name three things, tell me which of the fields it belongs to:
* Numbers
* Functions
* Variables
@@Bliss467 That's always my response to people who say they've never needed algebra after high school ... I deal with algebra every single day and I am *not* (directly, at least) a mathematician!
you guys, overloading is just regular english. It's not specialized jargon, it can be used in any field/industry/what-have-you.
I am actually surprised, that over so long time of the show running, we have not encountered graph topics. Isn't it interesting? This is a whole new dimension of videos coming on this topic :)
Title: Planar Graphs
Thumbnail: *is not a planar graph*
but it is one of the two key subgraphs that help distinguish planar vs non-planar
Strictly speaking, a thumbnail is a digital image consisting of some number of pixels organized in a N x M grid. Depending on what you think the most natural way to connect the vertices is (for example, connecting each pixel to the next pixel in its row and connecting the last pixel in a row to the first pixel in the next row, or simply connecting the pixels in a lattice), I'd argue that any thumbnail is in fact a planar graph.
Of course, you can go on to say that a digital image is nothing but a sequence of bits, or that a sequence of bits is nothing more than a series of voltage measurements, or that a series of voltage measurements is just a bunch of particles moving around in particular ways we've ascribed meaning to. In that case I think we've got bigger concerns than whether a graph is planar, but it certainly would provide an interesting discussion.
@@cizdramasnedalm8055 Ok, Neil deGrasse. Technically what I'm saying here are just pixels in a grid, so do interpret the following pixels- "pedantic asshole"- however you want.
@@oliverhoare6779 Hey friend, there's no need to get all upset over a simple comment. I was just being pedantic for the sake of humor. Admittedly, the humor might have not been all that amazing, but still I don't feel like I deserved that.
@@cizdramasnedalm8055 Fair enough, my bad
Heh, I remember very well when four colors theorem was a mere conjecture, and pretty notorious one.
ok boomer
@@Zeus.2459 :o)
When she started drawing them I got traumatic flashbacks of tree(3)
Did you take a pass on tree(graham's) ?
@@rcb3921 Sorry, I blanked out for a moment. Did you say something per chance?
So you weren't amazed? What's your problem? Brain function overload? Not enough space for input?
@@rcb3921 tree(tree(3))
@@WTFAnimatonsHD RAYO(TREE(G64))
We need a supercut of Numberphile videos that is just a series of all the times someone references Euler. Maybe another collab with Boyinaband to turn it into something musical.
2:28 Hipity Hopity Does this graph have this property?
6:52 I swear there's an Euler's formula in every scientific topic ever...
Basically. We should start numbering them.
The generally accepted naming convention for things in mathematics is that theyre named after the first person to discover them after Euler did
@@probablyabsent326 i laughed at this harder than i should have
Or is there? 🤨
This is why we need a meme of ben stein from ferris buelers day off. Saying euler? Euler? .....
This is perfect timing. Watching this litterally 1 hour before i'm going to learn this in my Discrete Mathematics lecture.
"it's a miracle"
We had a separate subject dedicated to Graph Theory.
I think my class is getting there soon.
Exactly the case with me lol. Just an hour before graph theory class.
I think the theorem around 13:55 is supposed to say "G is a planar graph and..."
+1. As a test, it is probably more straightforward to think of the contrapositive of the theorem: If E > 2V-4 (where V>=3) and there are no triangles, then the graph is not planar.
You're exactly right I've checked!
A while ago i found a game, called "untangle" (the main story is to free a kite, that is stuck in a tree), where the player has to untangle a mesh of vertices, that no lines are intersected without being connected to a vertex at this point.
There are multiple levele, where these mashes should display tangled parts of the kitestring.
Actually it´s taking a scrambled graph and transform it into a planar projection.
Is Prof Chudnovsky related to the Chudnovsky brothers (of Chudnovsky Algorithm Fame)?
We're learning this in discrete math right now, super cool
Thought i was going to sleep
Time to learn boys
how do you learn a boy
time to fail no nut November
The last graph doesn't seem so cheaty if you think about something like a subway map. Only five stations in the city center are densely connected and most stations are only along one route, but that is enough that you can't build it without expensive crossing tunnels.
Do you know Matt Parker's video about the Tube Knot in London?
Last time I was this early Euclid was still thinking about his postulates
I'm not sure why that sounds so dirty. Maybe Euclid explain it.
@@Jacquobite underrated joke
This is also a game: Untangle from Simon Tatham's portable puzzle collection
learning some of the things on this channel while in a lower level us math class is absolutely phenomenal... i dont understand it all but boy do i try to.. it seems like magic how simple//complex some if these things are and you can tell how completely the person presenting understands them and its mind boggling
Have a discrete math exam in a week so this is nice.
Thanks!
I’ve played a few games on the App Store about “untangling” strings, might be interesting for those looking to play with planar figures.
One of those games is called Planarity
delightful. thank you. your videos are a gift to the world and fill me with hope knowing people like you and these academicians are out there doing what you all do. thanks again.
I liked the respectful questions , unusual in modern times
I love your videos, now taking discrete math course in Taiwan.
The K3,3 graph can be embedded on a torus. What surface can the K5 be embedded in?
Sphere ?
@@frankstevenson5013 Nop, a 🍩.
Also a Möbius strip. In fact, you can put K_6 on a Möbius strip and K_7 on a torus.
@@frankstevenson5013 For any (finite?) graph on a sphere, find a blank spot and "pop" the sphere. You can map the rest to a plane, with the distortion being irrelevant in a graph sense.
For every n there exists a g so that Kn is embeddable in Fg, n and g being natural numbers. Same for Fg'.
As Tom Kerruish said, even the K7 is embeddable into a Torus (F1). The K8 is not. If you take three edges out of K8, that form a triangle, the graph you get is a minimal non embeddable graph for the Torus. So taking away one more edge will allow for an embedding. The Torus has alot more minimal Graphs. Not just two, like the 2-sphere or R^2.
In portuguese we have different names for those 2 kinds of graph. The one with x and y coordinates is a gráfico. The other is a grafo
Oooooo, graph theory! :D A surprisingly useful and beautiful branch of mathematics.
Nice to see world class expert on graphs here
At 13:54 it should be "If G *is* planar and has no triangles, then E
Great video! Just finished planarity in my 4th year graph theory course.
This is exactly what we've been working on in my discrete math class for the last 3 weeks.
Nitpick just so students watching this don't get lost looking at some other source:
around 12:50 when it's said that V is the # of verts and E is the # of edges, this is not standard. V is the set of vertices, and E is the set of edges. |V| is then the cardinality (size) of the set V (i.e. the number of vertices) and |E| is the cardinality of the set E.
Was just getting curious about graph theory! Really great talk by the professor!
Happy 8th birthday Numberphile!
numberphile is such a good channel
that comment @ 12:27 was so insightful
Happy Birthday, Numberphile!
Seems like something to keep in mind when planning PCB layout
But I believe that it is to much information to compute, if you have more than one copper layer. Because then we don't have planar graphs...
@@codecrafter151 having only just found out about this I cant be sure, but as far as I can see you only need to make sure that each individual layer contains no non planar graphs. I'd have to try finding more information about it to see how 'easy' it is though
12:47 what about two vertices and one edge?
That inequality is only true for (simple, connected) planar graphs with at least 3 vertices. They forgot to state that prerequisite.
8:28 bruh
🅱️RUH MOMENT
he said 'right'
Awesome video! Planar graphs are really interesting. 👍
The first square of 2 is 4. Higher power may be used. 3 and 5 adjacent. If you need higher Dimensions.
at 14:30 a perhaps better way of saying it would be: if you pick any three vertices of a K3,3 graph at least 2 of those vertices must come from the same side and therefore have no edge connecting them
Therefor its a P3L3
I was working on transition-metal complexes that had a non-planar graph in its base structure a couple of years ago.
My former Prof. really wanted to coin the term Kuratowski-complexes for these kinds of complexes.
That's my professor!
In the theorem at 12:58 shouldn't it say "G *is* planar" ?
The theorem saying for a planar graph, E ≤ 3V-6 apparently needs clarification since while the graph K2(two vertices joined together by one edge) is planar, the equation does not hold for this graph as shown here:
1 ≤ 3(2)-6
1 ≤ 0 (Not True)
V should be at least 3
"Those houses are actual houses, they're not these houses?"
that instrument at the wall is Rababa or Rebaba it is an old Arabic one string instrument :)
literally what i am learning in university now!
It's pretty useless...what you gonna use this for?
@@brunogallego7507 Graph theory is very useful in certain sectors of computer science and linguistics
@@brunogallego7507 That's not what maths is about... People like galois also didn't find a use for group theory, years later people found huge practical potential in that
@@brunogallego7507 Graph Theory has a wide range of applications and it forms the foundation for many algorithms in computer science. Look up the 'Koenigsberg Bridge Problem'
love the brown paper being taped up on the wall like a whiteboard but it's over a real whiteboard
Lets draw 20 million tree graphs
All tree graphs are planar graph
Why only 20 million? Why not ALL
LOL
Teach me more about graphs and embeddings!
Wow! This is so cool!!! This is a great way to think of the planar symmetries.
i already watched the entire video. top that!
Physically impossible!
Lol
I can't top that but I can say you are cute.
That is all,I'm leaving now.Have a nice day.
Bloke with a female profile...
@@jimdestiny7609 you fell for the simplest of traps
It is oddly satisfying to know that a pentacle is non-planar.
Glad to know which occult you like.
Is there any crazy 3d version of this, where some infinite graph is not 3d embeddable but would be in 4d? It would have to be real weird, but space filling curves are a thing...
I think so - I recall seeing a K3, 3 planar embedded using a Klein bottle as it's 2d space (on some 4chan post I think). Not 100% it's actually valid but on a glance it looked like it worked.
The only channel i subscribed only by watching one video
Is there a three dimensional equivalent of this? In three dimensions, K5 would work (picture a tetrahedron with a centerpoint), but would other graphs be impossible?
Yes! Instead of embedding (drawing) your graphs on a plane you could consider drawing them on any surface! In particular, instead of a plane you could embed them into the surface of a 3D object, like a sphere (which turns out is the same as the plane) or a donut. You could also imagine embedding them IN the 3D (or n-dimensional) object instead of just on the surface, but then you can draw any finite graph. Up to certain properties, each of these surfaces have their own "list" of smallest graphs that can't be drawn on them. A very amazing theorem (called the "Graph Minors Theorem") tells us that each of these lists contain a finite number of graphs. However, for most surfaces we don't know what those graphs are (or even how big the lists are)
3:00 -- SO YEAH, this particular graph is NOT PLANAR, *BUT* the number of vertices has a numerical relationship with the number of points where multiple lines cross. So -- are some non-planar graphs fractal?
No reference to the coffee mug with the 3 houses/utilities?
Hello, how many chromatic number of (c7) power 2 ????
Thanks for your nice lecture, is the empty graph (graph with no edges) a planner graph?
Awesome into and overview of the topic.
keep the good work going Brady
Where do they buy this brown paper?
could it be said that all graphs are planer embedded if they are in their natural dimension?
How many colours are needed to colour the map of all the countries (as recognised by a majority of UN member states right now) if external territories are coloured the same as the main country?
You should do a whole follow-up video on Robertson-Seymour theory! And with the SSCG function, you can tie it in with TREE(3) too. 🙂
I went through my algorithms class in college three times and no one explained this concept as simply as this video.
Unrelated but what’re the most interesting two digit numbers?
Decision maths has never been so accessible.
If only I had this a few years ago
James Blenkinsopp it's never too late, at least this is what I tell myself.
At 14:05, shouldn't that be "G is planar, ..." instead of "G is not planar, ..."?
It's like understanding ordered stack action.💚
how do you get e
I really like that you clearly know what a graph is (I've been watching this channel for a while, I'm sure you've heard of graphs). But you can still ask good, basic questions, so that your guest can give their explanations.
Also, is it just me or does Leonard Euler's face looks a little bit like Matt Parker's ?
You can tell when he gets to questions he really doesn't know, because he finds the answers cool 😁
Parker graph shirt?
Alternate title: "Summoning Satan with Math!" ;p
Learning basic graph theory for a tutoring interview... I got a notification for this video that just happened to be released today literally the same minute I started learning about planar graphs.
What were the names of the last 2 theorems ?
I can see how planar graphs would have many practical applications.
Imagine a PCB with components soldered on like capacitors, resistors, transistors, etc. Copper lanes need to connect various components but the lanes are not allowed to intersect.
This is a mix of four color theorem, tree3, the utility mug, and knot theorem
Now, the K3,3 graph, I remember this. My Question is : Why only take advantage on 1 side of the plane? If you use Both sides of the plane it is solvable (via a tunnel, or on circuit boards it's called a 'via'). The bridge to terabithia..
Planar graphs are very important in circuit architecture. You cannot have connections between components that intersect.
Given a graph, is there a test that it does have a K3,3 or K5 subgraph?
On wikipedia for "Planarity Tests":
_"Most of these methods operate in O(n) time (linear time), where n is the number of edges (or vertices) in the graph, which is asymptotically optimal."_
Really, one looks for subdivisions of those graphs (because this is the interesting property for planarity). Note in particular:
_"Algorithms that locate a Kuratowski subgraph in linear time in vertices were developed by Williamson in the 1980s."_
What a beautiful video, so elegantly interviewed and helpfully explained.
K-12 Student: Learns about graphs
K-12 Student: Leaves school
K-12 Student: *Sees the mathematical graphs*
K-12 Student: We're not in Kansas anymore
There's a fun puzzle here: given a graph, find a planar embedding. Google for Simon Tatham's Puzzles, and the puzzle in that collection is called "untangle". The number of hours I've spent on that...
I'm having this app for years, playing many puzzles, but I rarely played untangle because it's more guessing than thinking. Do you have any tricks or so?
@@mirkoschultz9347 It's a lot more about getting things mostly roughly right and refining later, rather than growing little areas of certainty like the other puzzles. Moving nodes close to the nodes they're connected to - if all the edges to a node form a sharp little angle, moving that node is a top priority. Doing some stuff like that to just make things nicer, before even thinking about untangling, really helps.
I wonder if there's going to be a special video when Numberphile hits 3.14... million subscribers?
I thought that there was a specific graph that actually required more than four colors.
I thought I'd heard of such a thing with maps some number of decades ago, but surely they'd know of it here by now.
You might be thinking of how you need seven colours for a map on a torus?
You might be thinking of the chromatic number problem, which is kinda related but not the same thing. And it's not a planar graph.
You may be thinking of the chromatic number of the plane (which would explain the confusion). Here the plane is seen as an infinite graph, where all points at distance 1 are adjacent. This graph is not planar (it contains a subdivision of K5), but we know that it needs between 5 and 7 colours to be properly coloured. The lower bound of 5 has been proven only recently with a very large subgraph of the graph of the plane, which needs 5 colours to be properly coloured.
Finally some graph theory. More!
K for komplete?
They're not completely unrelated, graphs both in graph theory and functional math are relations right?
Haha, I suppose so. But I don't think the etymology has anything to do with that - they're both things you draw, hence "graph"
This is related to Graham's number, isn't it?