Question

Let \(G\) be a planar graph with vertex-set \(\left\\{v_{1}, v_{2}, \ldots, V_{n}\right\\}\), and let \(p_{1}, p_{2}, \ldots, p_{n}\) be any \(n\) distinct points in the plane. Give a heuristic argument to show that \(G\) can be drawn in the plane in such a way that the point \(p_{i}\) represents the vertex \(v_{p}\) for each \(i\).

Short answer

The problem involves the properties and definition of a planar graph, and any n vertices of the graph can be drawn to correspond with n distinct points in the plane. This is because a planar graph can always be embedded in the plane without any edges crossing. The unique one-to-one correspondence between vertices and points together with the planar nature of the graph ensures that the graph can be drawn such that each vertex \(v_{i}\) corresponds to a unique point \(p_{i}\) in the plane.

Step-by-step solution

Understanding the concept of a planar graph

The first step is to grasp what a planar graph is. A planar graph is a graph that can be embedded in the plane, i.e., it can be drawn in such a manner that no edges intersect each other. An embedding of a graph in the plane is said to be proper if every edge connects two distinct points (its endpoints) and inside every face, the boundary connection is a simple cycle. So, the vertices \(v_{1}, v_{2}, ..., V_{n}\) of our planar graph G can be represented by distinct points \(p_{1}, p_{2}, ..., p_{n}\) in the plane.

Establishing a mapping for the vertices and points

The next step is to establish a mapping from the vertices of G to the points in the plane. For every vertex \(v_{i}\) in the graph G, assign it to a unique point \(p_{i}\) in the plane. This forms a one-to-one correspondence between the vertices of the graph and the points in the plane. Ensure no two different vertices are mapped to the same point.

Drawing the edges of the graph

After mapping the vertices of the graph to the points in the plane, the next step is to draw the edges of the graph. Draw a line segment between two points if there is an edge connecting the corresponding vertices in the graph. Since G is a planar graph, these line segments can always be drawn such that they don't cross each other in the plane.

Arguing the heuristic

It is true that there may be multiple ways to draw the graphs corresponding to different embeddings. However, there must exist at least one proper embedding due to the nature of planar graphs. The mappings ensure every vertex gets represented by a distinct point, and the condition that G is planar allows for an arrangement where no edges intersect. This heuristic argument demonstrates there will always exist a drawing of the planar graph G where each vertex \(v_{i}\) is represented by a corresponding point \(p_{i}\) in the plane.

Key concepts

Graph Embedding

Graph embedding is a fundamental concept in the study of graph theory, particularly when dealing with planar graphs. It refers to the process of laying out the vertices and edges of a graph within a given space, such as a plane, without violating certain rules. Specifically, for a graph to be properly embedded into a plane, each vertex must correspond to a unique point, and edges must be drawn as curves connecting the vertices without intersecting each other, except at their endpoints.

In educational terms, think of graph embedding as the art of sketching a network of friends at a party where paths (edges) between them don't cross. Each friend is a vertex, and they are scattered across the room (plane), with paths showing who can directly see whom without any obstacles (other paths) in the way. Being able to visualize this scenario helps students understand why embedding is crucial: it allows for a clearer, unambiguous representation of relationships (edges) between entities (vertices).

Planar Graph

A planar graph is like a friendship network that can be laid out on a single flat surface, say a wall, with no friendships (edges) crossing over each other. More technically, a planar graph is a type of graph that can be embedded in the plane so that its edges only intersect at their endpoints. The main characteristic of a planar graph is its ability to be drawn in such a way that no two edges cross.

This characteristic is significant because it simplifies many problems in graph theory. For example, imagine trying to understand road maps if highways could magically pass through each other without interchanges; it would be much more confusing. Teaching planar graphs helps students appreciate the clarity and simplicity that comes with well-organized systems, which can be particularly useful in fields like urban planning or network design.

Graph Vertices Mapping

Mapping the vertices of a graph to points in the plane is a crucial step in graph embedding. This mapping is like assigning seats to guests at a wedding: each guest (vertex) gets a specific seat (point), and just like you wouldn't want any two guests to share a seat, no two vertices should map to the same point. This one-to-one correspondence ensures that each entity represented by a vertex has a unique position on the drawing, aiding clarity.

During instruction, emphasizing the importance of unique assignments in vertex-to-point mappings can help students avoid mistakes and confusion in their graph drawings. It's much like ensuring every player in a board game starts on a different space; it sets the stage for the game (or in our case, the graphical illustration) to be played out smoothly.

Edge Intersection

Edge intersection is a critical concept to avoid when creating a planar graph embedding. If friends at a gathering want to pull a string between them to show their connection without creating a tangled mess, they will need to make sure these strings don't cross. Similarly, in graph drawings, edges should connect vertices without overlapping with other edges except at the vertices themselves.

Understanding edge intersections is essential for students as it can complicate both the representation and interpretation of graphs. It's similar to driving: roads interconnecting without proper intersections (like overpasses and underpasses) can lead to accidents. In graph theory, ensuring no unnecessary intersections lead to clearer and more accurate representations of the relationships within the graph, which is crucial for problem-solving and analysis.