What are Planar Graphs? | Graph Theory

What are planar graphs? How can we draw them in the plane? In today's graph theory lesson we'll be defining planar graphs, plane graphs, regions of plane graphs, boundaries of regions of plane graphs, and introducing Euler's formula for connected plane graphs.

A planar graph is a graph that can be drawn in the plane with no edge crossings. A plane graph is a planar graph that has been drawn in the plane with no edge crossings. Thus, a graph being planar is not dependent on how it is drawn, but only on how it CAN be drawn, whereas a graph being a plane graph is dependent on how it is drawn. The complete graph K4 can be drawn as a plane graph and is thus planar, but can also be drawn not as a plane graph.

A nonplanar graph is a graph that cannot be drawn in the plane without edge crossings. That is, a nonplanar graph will always have edge crossings if drawn in the plane. An example of a nonplanar graph is K3,3 the complete bipartite graph with two partite sets of cardinality 3.

A plane graph divides the plane into different regions. The subgraph, comprised of vertices and edges that are incident with a region, make up the boundary of the region. The boundary of a region is also sometimes defined (roughly) as the closed walk that encloses a region.

In a connected plane graph, the number of vertices (n), minus the number of edges (m), plus the number of regions (r), that is: n-m+r, is equal to 2. This is Euler's formula for connected plane graphs.

I hope you find this video helpful, and be sure to ask any questions down in the comments!

+WRATH OF MATH+

Follow Wrath of Math on...

[WrathofMath]

Support the production of this course by joining Wrath of Math as a Channel Member for exclusive and early videos, original music, and upcoming lecture notes for the graph theory series! Plus your comments will be highlighted for me so it is more likely I'll answer your questions!

[SYLXM]

I sit in class feeling like a failure for not being able to understand this stuff, and then you clear up the topic nearly every time. Your series on graph theory have been an absolute savior. You are so good at describing these concepts, I wouldn't be surprised if you used a teleprompter! Such elegant explanations.

[lucassilva]

exams are in a week. This channel helped me a lot. Especially when my teacher made all of discrete math seem so complicated when it was just this simple and understandable. Thanks a lot man.

[jack-cije]

This video came out a few days after my discrete math final lol I needed this

[igorsun]

the two moments you came up with EulerIdentity and examples of non-planar are just How interesting they are woah!

[rominamehrabi]

You just saved my assignment's life, Thank you!

[Vanshika-rzok]

Your teaching methods are good and I am from India

[HIRANYAKSHIKSHIRSAGAR]

your explanation is thankyou so much sir.

[sourabhahegde]

Thank you so much! I have an exam tomorrow and you are a life saver!

[ChocolateMilkCultLeader]

You are a great great person. Thank you

[PunmasterSTP]

It's plane to see: your channel's awesome! 👍

[mzarinchang]

The vertices of same color should be adjacent or should not?

[chittytherobot]

wow ! why werent you my TA in school for the Graph Theory course ! loved your video this is absolutely awesome. BTW - How is it possible to draw K33 on a coffee cup, wouldnt I still end up crossing the final edge ? ( or am I doing something goofy like .. drawing over the handle of the cup ?)

[mike_the_tutor]

Do you have any interest in graceful graphs? If so, I suggest a video on the classes which have been proven graceful. I haven't dug into those proofs myself, but I assume they're difficult. However, many classes have been proven by construction, or in other words, an algorithm for labeling the vertices. That makes it easy to demonstrate the algorithm on examples, even if the formal proof is too difficult to explain. Just another thought. As always, take it or leave it. Keep enjoying the math and stay swanky!

[Ahadi]

Please explain Cage- amalgamation graph, how we cane find it?
thanks

[Ahadi]

Hello sir, please explain weakly modular graphs and its properties
!

[atiehgebrine]

can we use euler formula to prove a graph is plannar?

[LearningCS-jpcb]

That outro is 🔥, gives vibes of math researcher playing key role in ww3 winning lmaoo

[أحمد-خنك]

Interesting thing about thus topic is that any nonplaner graph, Must containe any of K3, 3 or K5 or both....

[cybervigilante]

I was looking at a couple of graph theory primers, and they both started with geographic areas. They mentioned the edges couldn't cross. What I want to know is Why the edges can't cross. What am I missing?