Graphs and Their Drawings
A graph is an abstract collection of vertices and edges; a drawing places them in the plane. The distinction matters because an awkward drawing can have crossings even when the same graph admits a crossing-free arrangement. To establish that a graph is planar, it is enough to give one valid crossing-free drawing. A drawing with a crossing, by itself, settles only that the particular drawing is not crossing-free.
Throughout, graphs are finite and simple. A curve representing an edge will be a simple arc: a continuous curve with no self-intersections. Vertices are represented by distinct points, and the arc for an edge \(uv\) joins the points for \(u\) and \(v\). Coordinates are a convenient way to specify some drawings, but edges are allowed to be curved in general.
Thus “planar” describes whether a suitable drawing exists, while “plane” refers to a particular drawing that has already been specified. A vertex is represented by a point, and an edge by its assigned arc. If two arcs cross away from their endpoints, that intersection is not a vertex of the graph. It remains a crossing in that drawing unless the graph itself is changed.
Checking a Drawing
For a coordinate drawing, check two kinds of conditions. First, no vertex point may lie in the interior of an edge that does not end there. Second, edge arcs must not intersect except at common endpoint vertices. For straight-line drawings, these checks can often be done using line equations and the segments’ coordinate ranges. It is not enough to notice that edges have different names: nonincident edges can still cross.
Worked Example: A Crossing Drawing of a Path
Let \(G\) have \(V=\{1,2,3,4\}\) and \(E=\{12,23,34\}\), so \(G\) is the path \(1,2,3,4\). Draw the vertices at \(1=(0,0)\), \(2=(4,4)\), \(3=(0,4)\), and \(4=(4,0)\), with straight segments for the edges.
The segment for \(12\) lies on \(y=x\), with \(0\le x\le4\). The segment for \(34\) lies on \(y=4-x\), also with \(0\le x\le4\). Their intersection satisfies \(x=4-x\), so \(2x=4\), \(x=2\), and \(y=2\). The point \((2,2)\) is in the interior of both segments, and \(12\) and \(34\) have no common endpoint. Thus this particular drawing has a crossing. The segment for \(23\) is the top horizontal segment from \((4,4)\) to \((0,4)\); it meets the other two segments only at its endpoints, \(2\) and \(3\).
The crossing point \((2,2)\) is not a vertex of \(G\): it is not in the vertex set, and the edge set still consists of exactly \(12,23,34\). Now redraw the same graph with vertices \(1=(0,0)\), \(2=(1,0)\), \(3=(2,0)\), and \(4=(3,0)\). The three edge segments are consecutive intervals on the horizontal axis. They meet only at their shared endpoint vertices, so this is a crossing-free drawing. Therefore \(G\) is planar, despite the crossing in the first drawing.
Check: the second drawing has four distinct vertex points and three segments, each joining the endpoints of one of \(12,23,34\). Consecutive segments meet at \(2\) or \(3\), their common endpoint, and nonconsecutive segments do not intersect.
Worked Example: Drawing \(K_4\) Without Crossings
Let \(G\) have \(V=\{A,B,C,D\}\) and \(E=\{AB,BC,CA,AD,BD,CD\}\). This is the complete graph \(K_4\). Place \(A=(0,0)\), \(B=(4,0)\), \(C=(2,3)\), and \(D=(2,1)\), and represent every edge by a straight segment.
The three edges \(AB,BC,CA\) form the boundary of a triangle. The point \(D\) is the average of the three outer points, since \(((0+4+2)/3,(0+0+3)/3)=(2,1)\). It therefore lies strictly inside that triangle. The remaining three edges \(AD,BD,CD\) are segments from the interior point \(D\) to the three distinct corners. Each stays inside the triangle except at its corner endpoint. Two of these segments can meet only at \(D\): they lie on distinct rays from \(D\), since their other endpoints are distinct corners. The three boundary edges meet one another only at \(A,B,C\), and no interior segment meets a boundary edge except at its own corner. There are no other edges to check. This drawing is crossing-free, so \(K_4\) is planar.
Check: the specified edge set has three boundary edges and three edges incident with \(D\), for a total of \(3+3=6\), as required for all pairs among four vertices. Each is represented once in the drawing.
Worked Example: A Crossing-Free Drawing of \(K_{2,3}\)
Let the vertex set be \(V=\{u,v,x,y,z\}\), with parts \(\{u,v\}\) and \(\{x,y,z\}\), and let \(E=\{ux,vx,uy,vy,uz,vz\}\). This is \(K_{2,3}\): every vertex in one part is adjacent to every vertex in the other, and there are no edges within either part.
Use the coordinates \(u=(0,0)\), \(v=(6,0)\), \(x=(3,3)\), \(y=(3,0)\), and \(z=(3,-3)\), and draw all six edges as straight segments. The two segments \(ux\) and \(vx\) lie above the horizontal axis except at \(u\) and \(v\), respectively; they meet each other at \(x\). The two segments \(uz\) and \(vz\) lie below the axis except at their respective endpoints, and meet each other at \(z\). The segments \(uy\) and \(vy\) occupy the intervals from \(0\) to \(3\) and from \(3\) to \(6\) on the horizontal axis; they meet at their common endpoint \(y\). The upper and lower segments cannot meet away from the horizontal axis because their interiors lie on opposite sides of it. An upper or lower segment meets a horizontal segment only at a shared endpoint \(u\), \(v\), or \(y\): the upper and lower segments meet the axis only at \(u\) or \(v\), and the horizontal segments meet each other only at \(y\). Hence the drawing has no forbidden intersections, and \(K_{2,3}\) is planar.
Check: there are \(2\cdot3=6\) edges between the two parts, exactly the six listed. No edge \(uv\) is present, so the fact that \(u,y,v\) are collinear does not create an edge passing through the vertex \(y\).
What a Drawing Can Establish
Proof. By definition, a graph is planar if it has at least one crossing-free drawing. Therefore a crossing-free drawing certifies planarity. If a drawing has a crossing, it fails the definition of crossing-free, so it is not a plane drawing. That fact concerns only the drawing under consideration; it does not rule out a different drawing of the same graph. The path example gives a direct instance: its first drawing has a crossing, while its second drawing is crossing-free. \(\square\)
The practical consequence is asymmetric. One valid crossing-free drawing is a complete certificate that a graph is planar. A failed attempt to draw a graph without crossings is not a certificate of nonplanarity. To establish nonplanarity requires an argument that rules out every possible drawing, not merely the one currently being inspected.
Proof. Suppose \(G\) is planar, and choose a crossing-free drawing of \(G\). To draw \(H\), keep only the points for vertices in \(V(H)\) and the arcs for edges in \(E(H)\); discard all other points and arcs. Every retained edge still joins its endpoints. Its interior avoided every vertex point in the original drawing, so it also avoids the retained vertex points. Two retained edge arcs intersect only where the original drawing allowed them to intersect, namely at a shared endpoint. Thus the remaining drawing is crossing-free and represents \(H\). This proves that \(H\) is planar. \(\square\)
In particular, deleting edges or vertices from a planar graph preserves planarity. This is a useful way to transfer a known drawing to a smaller graph: retain only the parts that are needed. The theorem does not say that every drawing of the subgraph must be crossing-free; it guarantees that at least one suitable drawing exists.
Proof. An isomorphism is a bijection between the vertex sets that preserves adjacency in both directions. Take a crossing-free drawing of the first graph. Assign each vertex of the second graph the point assigned to its corresponding vertex under the bijection, and assign each edge the arc of its corresponding edge. Since adjacency is preserved, these arcs have exactly the correct endpoints. The vertex points remain distinct, and the arcs have the same intersections as before, so the resulting drawing is crossing-free. Thus planarity of the first graph implies planarity of the second. Applying the same argument to the inverse bijection proves the converse. \(\square\)
Common Pitfall: Promoting a Crossing to a Vertex
A frequent error is to treat every intersection in a drawing as a graph vertex. In the crossing drawing of the path, one might insert a new point \(w=(2,2)\) and say that the two crossing edges have split into \(1w,w2\) and \(3w,w4\). But that describes a changed graph: it has the additional vertex \(w\), and the original edges \(12\) and \(34\) have been replaced by four edges. Including the unchanged edge \(23\), this new graph has \(5\) vertices and \(5\) edges, whereas the original path has \(4\) vertices and \(3\) edges.
The correction is to follow the specified vertex and edge sets. In the original graph, the crossing is not a vertex and the edges remain \(12,23,34\). If an intersection is intended to be a vertex, the graph must explicitly include that vertex and the altered edges. The drawing and the graph are related, but they are not interchangeable descriptions.
When deciding whether a graph is planar, state the graph explicitly and describe the proposed drawing well enough to check all intersections. Coordinates are one option; a precise description of arcs is another. Verify vertex points, edge endpoints, and every possible intersection. A single verified crossing-free drawing proves planarity; a single crossing drawing does not prove nonplanarity.
Check Your Understanding
For each question, distinguish the abstract graph from the drawing used to represent it.
- In a drawing of \(P_4\), two nonincident edge arcs cross. What does this establish, and what does it not establish?
- Explain why the coordinate drawing of \(K_4\) above has no edge passing through \(D\) other than edges incident with \(D\).
- Give the vertex set and edge set of the graph obtained by replacing the crossing of edges \(12\) and \(34\) in the first path drawing by a new vertex.
- Why does retaining only some vertices and edges from a crossing-free drawing give a crossing-free drawing of the corresponding subgraph?
- If a graph is planar, must every straight-line drawing of it be crossing-free? Explain the distinction between “planar” and “plane.”