Faces as Available Regions
A planar graph is one that admits a drawing in the plane with no edge crossings. A plane graph is a particular such drawing, so its faces and their boundaries are part of the data. When considering whether an edge can be added to a plane graph without crossings, the relevant question is not just whether its endpoints are vertices of the graph: it is whether they can be joined through one of the regions left open by the drawing.
All graphs in this tutorial are finite and simple. A plane embedding draws vertices as distinct points and edges as arcs that meet only at shared endpoints. The faces are the connected regions of the plane not occupied by the drawing; one is unbounded. A vertex is on the boundary of a face if it belongs to the closure of that face. For a connected plane graph, the boundary of a face can be described by a boundary walk, in which vertices or edges may repeat. For a disconnected plane graph, a face can have more than one boundary component, so one boundary walk need not describe its entire boundary.
A bridge that is just one edge has exactly two distinct attachments. For such a bridge, being on a common face boundary is both necessary and sufficient to add it to the fixed embedding without crossings. For a larger bridge, having all attachments on a common face boundary is necessary, but not in general sufficient: the bridge must also be drawable inside that face. This distinction is essential when applying the face test.
The Common-Face Criterion for an Edge
Proof. First suppose the edge \(uv\) has been drawn without crossings. Apart from its endpoints, the drawn arc avoids \(H\). Its interior is connected, so it lies entirely in one component of the complement of the drawing of \(H\), namely one face \(F\). Points of the arc approach \(u\) and \(v\) through \(F\), so both vertices belong to the boundary of \(F\).
Conversely, suppose \(u\) and \(v\) are both on the boundary of a face \(F\). Since \(u\ne v\), choose small neighborhoods of the two vertices in which arcs can enter \(F\) without meeting the drawing of \(H\). The face is an open connected subset of the plane, hence it is polygonally path-connected. Join the two neighborhood arcs by a path lying in \(F\). If that path repeats points, remove the portions between repeated points; this gives a simple arc from \(u\) to \(v\) whose interior lies in \(F\). Drawing \(uv\) along this arc creates no crossing with \(H\). Thus the edge can be added without crossings. \(\square\)
The theorem concerns the fixed embedding of \(H\). If \(u\) and \(v\) share a face, a route through that face works; if they do not, no route for a new edge can avoid the existing drawing. It does not say that every pair of vertices can be joined in every embedding of the same abstract graph.
Applying the Test to Explicit Embeddings
Worked Example: Adding a Diagonal to a Square
Let \(H\) have \(V(H)=\{1,2,3,4\}\) and \(E(H)=\{12,23,34,41\}\). Embed this cycle as the boundary of a square, with vertices \(1,2,3,4\) in that cyclic order. The faces are the interior of the square and the unbounded exterior; each face has all four vertices on its boundary. Can the edge \(13\) be added?
The endpoints \(1\) and \(3\) lie on the boundary of the interior face. By the theorem, \(13\) can be drawn there without crossing \(H\). For an explicit drawing, draw it as the diagonal from \(1\) to \(3\). The interior face is split into the two faces with boundary walks \(1,2,3,1\) and \(1,3,4,1\); the unbounded face is unchanged.
Check: the new edge has endpoints \(1\) and \(3\), and its interior lies strictly inside the square. It therefore meets the existing boundary only at its endpoints. The new edge set is \(\{12,23,34,41,13\}\), so the added edge is exactly the diagonal just described.
Worked Example: Choosing the Exterior Face
Let \(H\) have \(V(H)=\{1,2,3,4\}\) and \(E(H)=\{12,23,34,41,13\}\), embedded as a square with diagonal \(13\) drawn inside. The bounded faces have boundary walks \(1,2,3,1\) and \(1,3,4,1\); the unbounded face has boundary walk \(1,2,3,4,1\). Can the missing edge \(24\) be added?
Vertices \(2\) and \(4\) do not lie together on either bounded face: the first has boundary vertices \(1,2,3\), and the second has boundary vertices \(1,3,4\). But both lie on the boundary of the unbounded face. The criterion therefore says that \(24\) can be added, using the exterior region. Draw it outside the square, from \(2\) around the outside to \(4\). Its interior does not meet the square or the diagonal.
Check: the new edge \(24\) meets the original drawing only at \(2\) and \(4\), so it creates no crossing. The edge set becomes \(\{12,23,34,41,13,24\}\); in particular, both diagonals are present, but they do not cross because they are drawn on opposite sides of the square.
Worked Example: A Pair That Shares No Face
Consider the octahedral graph with vertex set \(V(H)=\{a,a',b,b',c,c'\}\). Its edges are all pairs from different parts of the partition \(\{\{a,a'\},\{b,b'\},\{c,c'\}\}\); explicitly, \(E(H)=\{ab,ab',ac,ac',a'b,a'b',a'c,a'c',bc,bc',b'c,b'c'\}\). For this embedding, draw the 4-cycle \(b,c,b',c',b\) as an equator, put \(a\) on one side and \(a'\) on the other, and join each of them to all four equatorial vertices. Choose one triangular region as the unbounded face.
Each face is a triangle consisting of one of \(a,a'\) and two consecutive equatorial vertices. Thus no face boundary contains both \(a\) and \(a'\). Since the edge \(aa'\) is absent from \(H\), the common-face criterion says it cannot be added without crossing in this fixed embedding. The fact that the two vertices are both on the sphere’s two sides of the equator does not help: the test concerns the boundary of a single face in the plane drawing.
Check: the face descriptions account for four triangles around \(a\) and four around \(a'\). Each has one pole and two equatorial vertices; none contains both poles. Hence \(a\) and \(a'\) do not share a face boundary, as required for the negative conclusion.
What the Test Says for Larger Bridges
Proof. In a crossing-free extension, the drawing of the bridge outside its attachment vertices avoids \(H\). For a bridge arising from a component of \(G-V(H)\), that component is connected, and the bridge edges join it to its attachments. Consequently the bridge, apart from the attachment points on \(H\), is drawn in one face of \(H\): a connected drawing disjoint from \(H\) cannot pass from one face to another without meeting \(H\). Each attachment is approached by the bridge through this face, so every attachment lies on its boundary. A bridge that is a single edge satisfies the same conclusion by the edge theorem. \(\square\)
This proposition gives a necessary test for a larger bridge, not a complete existence test. The interior structure of a bridge can itself prevent an embedding. For instance, a bridge may contain a nonplanar subgraph even when all its attachments lie on one face. In general, one must check both the common-face condition and whether the bridge can actually be drawn in that face while meeting \(H\) only at its attachments.
Worked Example: Common Attachments Do Not Ensure a Drawable Bridge
Let \(H\) consist of five isolated vertices \(V(H)=\{x_1,x_2,x_3,x_4,x_5\}\) and \(E(H)=\varnothing\), drawn as five distinct points in the plane. Its unbounded face has all five vertices on its boundary. Let \(B\) have additional vertices \(y_1,y_2,y_3,y_4,y_5\), all ten edges \(y_i y_j\) with \(1\le i<j\le5\), and the five edges \(x_i y_i\) for \(1\le i\le5\). Thus \(B\) is an \(H\)-bridge whose attachments are \(x_1,\ldots,x_5\).
All five attachments lie on the boundary of the same face of \(H\), so the necessary attachment test is passed. Nevertheless, \(B\) cannot be added to this plane embedding without crossings: its subgraph on \(\{y_1,y_2,y_3,y_4,y_5\}\) is \(K_5\), which is nonplanar. Any crossing-free drawing of \(B\) would restrict to a crossing-free drawing of that \(K_5\), contradicting the nonplanarity of \(K_5\).
Check: the edges among the five \(y_i\) are exactly all ten pairs, so the indicated subgraph really is \(K_5\). The five edges \(x_i y_i\) make each \(x_i\) an attachment. Thus the failure is internal to the bridge, not a failure of the common-face condition.
Common Pitfalls
Do not use the condition in the wrong direction. For a single new edge, common-face boundary membership is both necessary and sufficient. For a general bridge, it is necessary, but the example above shows it is not sufficient. A common face provides the region in which a bridge might be drawn; it does not make a nonplanar bridge planar.
Do not confuse a face with one boundary walk. In a connected plane graph, a face boundary can repeat vertices or edges. In a disconnected plane graph, a face may have multiple boundary components. The test is about whether the attachments lie on the boundary of one common face, not whether they appear together in a single simple cycle.
Do not test only the bounded faces. The unbounded face is a face too. In the square-with-diagonal example, the missing edge \(24\) cannot be added through either bounded face, but it can be drawn through the unbounded face. A valid test checks every face of the fixed embedding.
The face criterion is useful because it converts a drawing question into a boundary-membership question. In arguments about bridges, it tells us where a bridge would have to go: all its attachments must be accessible from one face. For an edge bridge, that condition settles the question completely. For a larger bridge, it narrows the possibilities and signals that the bridge’s own structure must also be considered.
Check Your Understanding
For each question, distinguish a single-edge bridge from a bridge with internal vertices.
- In a plane embedding, what condition on the endpoints is necessary and sufficient for adding a missing edge without crossings?
- Why can a connected bridge that has been added without crossings have attachments on only one face boundary?
- In the square with diagonal \(13\), which face allows the addition of edge \(24\)?
- Why does the octahedral embedding described above rule out adding edge \(aa'\) without crossings?
- Give a reason, other than the attachment locations, that a larger bridge might fail to be drawable in a face.