2
$\begingroup$

A polyhedral embedding of a graph on a surface is an embedding without edge crossings such that all the faces are bounded by simple cycles, and any two faces share a common vertex, share a common edge, or do not intersect at all. Moreover, all the faces are disks.

Given a graph $G$ with a polyhedral embedding on a surface $S$, one can define a dual graph $G'$ embedded in the same surface $S$, by creating a vertex in $G'$ for each face of $G$, and adding an edge between two vertices of $G'$ for each edge that the corresponding two faces in $G$ share.

I have a feeling that this will be simple, but I don't know how to prove it, so here it goes anyways. Question: The dual embedding that one obtains for $G'$ is also polyhedral?

$\endgroup$
7
$\begingroup$

You need to specify that $G$ is a simple graph (else the trigonal hosohedron is a counterexample) but then the answer is yes. What can go wrong? If a dual face is not a simple cycle then one of its edges is repeated, giving a self-loop in the primal, or a vertex but not an edge is repeated, in which case this face and vertex form a configuration of the same type in the primal. If two dual faces meet at more than one edge then there is a multiple adjacency in the primal. If the dual has a self-loop or multiple adjacency then we get a face with a repeated edge or two dual faces meeting at more than one edge in the primal. If two dual faces meet at two vertices but do not share an edge between these two vertices then a configuration of the same type happens in the primal. And if two dual faces meet in an edge and a third vertex then in the primal we have three faces sharing the same two vertices and they can't all three contain the edge connecting these two vertices.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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