Planar graph

Imagine drawing dots and lines on a flat paper.

Some shapes are special. You can draw them so no lines cross each other. These are called planar graphs.

You can also draw these shapes on a ball.

A shape that fits on a ball is also planar.

Some shapes are hard to draw. They must have crossing lines.

These shapes are not planar.

Math can help us find these shapes. We can use rules to check them. These rules help us know if lines will cross.

It is fun to see how shapes fit together.

Imagine drawing dots and lines on a flat sheet of paper.

Some shapes are special. You can draw them so no lines cross each other. We call these planar graphs.

If you can draw a shape on a ball without lines crossing, it is also planar.

This is because a flat plane and a sphere are very similar in math.

Some shapes are not planar. They must have crossing lines no matter how you draw them.

One such shape is called K5. Another is K3,3. These are called forbidden graphs. If a shape contains these, it cannot be planar.

There is a famous rule called Euler's formula. It helps us understand how these shapes work. It uses three numbers. These are vertices, which are the dots. Edges are the lines. Faces are the empty spaces between the lines.

For any planar graph, the dots minus the lines plus the faces always equals two. This is a steady rule that stays the same. It works for many shapes, even solid objects like a cube.

Every planar graph has a partner called a dual graph. We make it by putting a new dot in each face. Then we draw lines to connect them. This helps math experts study new shapes.

Imagine drawing dots and lines on a flat sheet of paper.

Some shapes are special because of how their lines behave. A planar graph is a shape that can be drawn so that no lines ever cross each other. The lines only meet at the dots, which mathematicians call vertices. If you can draw a shape on a flat surface without any lines jumping over one another, it is planar. This same rule works if you draw the shape on a ball, or a sphere.

This is because a flat plane and a sphere are very similar in the world of math.

Not every shape can be drawn this way. Some shapes are impossible to draw on a flat surface without lines crossing.

Mathematicians have found specific shapes that act like rules. If a shape contains these special patterns, it can never be planar. One such pattern is called K5. Another is called K3,3, which is sometimes called a utility graph.

A famous mathematician named Kazimierz Kuratowski proved that these patterns are the reason some graphs fail to be planar. Another thinker named Klaus Wagner also found ways to identify these forbidden shapes using a method called minors.

There is a wonderful rule that helps us check these shapes. It is called Euler's formula. This formula uses three numbers: the vertices (dots), the edges (lines), and the faces (the empty spaces trapped between lines).

For any connected planar graph, the number of vertices minus the edges plus the faces always equals two. This is a steady truth that stays the same no matter how you change the shape. For example, in a butterfly graph, there are 5 vertices, 6 edges, and 3 faces. If you do the math, 5 minus 6 plus 3 equals 2. This rule even works for solid objects like a cube!

Planar graphs also have a special relationship with circles.

There is a rule called the circle packing theorem. It says that every planar graph can be shown as a collection of circles that touch but do not overlap. When circles touch at exactly one point, we say they "kiss." This helps us see that every planar graph can be drawn using only straight lines for its edges. This discovery is known as Fáry's theorem. It shows how neat and organized these shapes really are.

Finally, every planar graph has a mathematical partner called a dual graph.

To find a partner, you place a new dot inside every face of the original shape. Then, you draw new lines to connect these dots. Each new line crosses exactly one of the original lines. This process creates a new graph that has its own special properties. The number of dots in the new graph is the same as the number of faces in the old one. This connection helps mathematicians study very hard problems by looking at the partner instead.

{ "text": "In the field of graph theory, a planar graph is a specific type of mathematical structure. It is a graph that can be embedded in a plane. This means it can be drawn on a flat surface so that its edges intersect only at their endpoints. In a planar drawing, no two edges ever cross each other. Such a drawing is formally called a plane graph or a planar embedding.

A plane graph maps every node to a point and every edge to a curve. These curves must be disjoint, meaning they do not touch except at the nodes they connect.\n\nPlanar graphs are not limited to flat surfaces. Any graph that can be drawn on a plane can also be drawn on a sphere. This is possible through a method called stereographic projection. Because the plane and the sphere are mathematically similar, they share these properties. In more advanced geometry, these graphs can be generalized to surfaces of a specific genus. A planar graph is considered to have a genus of 0. This is because both the plane and the sphere are surfaces with a genus of 0.

\n\nMathematicians use several rules to determine if a graph is planar. Kazimierz Kuratowski developed a famous characterization known as Kuratowski's theorem. He proved that a finite graph is planar if and only if it does not contain a subgraph that is a subdivision of the complete graph K5 or the complete bipartite graph K3,3. A subdivision occurs when you insert new vertices into existing edges.

Klaus Wagner provided a different perspective through Wagner's theorem. Instead of subdivisions, he focused on graph minors. A minor is created by taking a subgraph and repeatedly contracting edges into single vertices. A graph is planar if it does not have K5 or K3,3 as a minor.\n\nThere are also mathematical formulas that provide necessary conditions for planarity. For a simple, connected, planar graph with $v$ vertices, $e$ edges, and $f$ faces, Euler's formula must hold true. The formula is $v - e + f = 2$.

This formula works for any such graph where $v$ is at least 3. For example, the butterfly graph has 5 vertices, 6 edges, and 3 faces. Calculating $5 - 6 + 3$ results in 2. This rule also applies to convex polyhedra. A Schlegel diagram can turn a polyhedron into a planar graph by projecting it onto a plane.

\n\nBecause of these rules, planar graphs are considered \"sparse\" graphs. This means they have relatively few edges compared to the number of vertices. For any simple, connected, planar graph where $v \ge 3$, the number of edges must follow the inequality $e \le 3v - 6$. If the graph has no cycles of length 3, the rule becomes even stricter: $e \le 2v - 4$. Furthermore, the number of faces must satisfy $f \le 2v - 4$. These inequalities help prove a graph is not planar, though they cannot prove that a graph is planar.\n\nAn interesting connection exists between planar graphs and geometry through the circle packing theorem. Proved by Paul Koebe in 1936, this theorem states that a graph is planar if and only if it is a \"coin graph.\" In a coin graph, vertices are represented by circles that \"kiss,\" or touch at exactly one point, without overlapping.

This theorem provides a way to prove Fáry's theorem. Fáry's theorem states that every simple planar graph can be drawn using only straight line segments for edges without any crossings.\n\nEvery planar graph also has a mathematical partner known as a dual graph. To build a dual graph, you place one new vertex in every face of the original graph, including the outer face. You then draw new edges that connect these vertices by crossing exactly one edge of the original graph.

The resulting dual graph has as many edges as the original, but its vertices correspond to the original's faces. This relationship is highly symmetrical, as the dual of a dual graph returns you to the original embedding. This connection allows mathematicians to study complex properties of one graph by analyzing its partner.", "media": [ "File:Butterfly graph.svg", "File:Dodecahedron schlegel.svg", "File:Complete graph K5.svg", "File:Biclique K 3 3.svg", "File:Circle packing theorem K5 minus edge example.svg", "File:Dual graphs.svg" ] }