1
$\begingroup$

To get the dual of a planar graph, each of the faces becomes a vertex. And then, two vertices in the dual graph are connected if they share a common face. My question is about planar graphs that have disconnected components. It's unclear to me how to define a face for these. As a simple example, consider the graph below.

enter image description here

What is the dual graph of this one and how many "faces" does it have?

$\endgroup$
2
  • 1
    $\begingroup$ The faces of an (embedded) planar graph are the connected components of the plane with the edges removed. In your case, there is a single face, and so the dual graph contains a single vertex with three self-loops. $\endgroup$ Apr 30, 2022 at 11:23
  • $\begingroup$ Thanks! This could have easily been an answer. $\endgroup$ Apr 30, 2022 at 16:33

1 Answer 1

1
$\begingroup$

First of all, the dual of a planar graph is only defined with respect to a planar embedding; for some planar graphs, every embedding gives the same dual graph (as a graph), but this is not always the case.

Given a planar embedding of a planar graph, a face is a connected component of the plane with the edges of the graph removed. In your case, after removing the edges, the plane remains connected, and so there is a single face. The dual of your graph thus consists of a single vertex with three self-loops.

The same dual graph would be obtained if instead of your graph we take a matching, a star with three edges, or a path of three edges. This seems to contradict the well-known result that the dual of the dual is the original graph. However, this result only holds for connected graphs (although both the star and the path are connected, the corresponding planar embeddings are different). For more on this issue, see this question.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.