So it is well known that given a planar graph, $G$, embedded in the plane (without edge crossing, so a planar embedding). One can construct the planar dual, $G^*$. What is perhaps slightly less well-known, and surprising, is that the resulting planar dual depends on the embedding. Not just the way in which the dual is embedded in the plane, but it's very graph isomorphism type can change with a different planar embedding of $G$. The easiest example to show this is a graph that looks like a rectangle with 2 triangles attached to opposite sides. This can alternatively be embedded with one of those triangles 'folded inside' the rectangle. Producing a different, non-isomorphic planar dual. This motivated me to ask: Is there a 'larger' abstract object which contains both of these (and more)? It turns out that I came up with just such an object.

Definition: Given a 2-edge connected graph, $G$, the duplex graph, $G^{\triangle}$, of $G$ is constructed as follows: 1. For each cycle, $C_k$ in $G$ (by which, I mean a set of vertices and edges which form a subgraph isomorphic to a cyclic graph with at least 3 vertices), create a vertex, $v(C_k)$. 2. For each pair of distinct cycles, $C_j,C_k$, If the intersection of their edge sets, $E(C_j)\cap E(C_k)$, is nonempty, then for each edge, $e_d$, in the intersection, $E(C_j)\cap E(C_k)$, create an edge $e_d^{\triangle}$, between $v(C_j)$ and $v(C_k)$.

The result is a unique, embedding independent, graph $G^{\triangle}$ for any suitable graph $G$. In investigating this object and some close relatives. I discovered deep connections between these objects and the general embedding problem on 2-manifolds for graphs (essentially, the topological genus question for graphs and related ideas). Some digging revealed this question is generally attacked via the theory of rotation systems (several papers on this that I found citations for were from the early 1980s). What I think I have here is an entirely different way of looking at this question that seems very interesting.

My question is this: Is this idea (of producing a more general object related to the planar dual) present in the literature? (I have not encountered it, but perhaps someone else has?) If so, was any connection to graph embeddings (especially other than planar) investigated with it?

  • $\begingroup$ Matroids: see en.wikipedia.org/wiki/Matroid. $\endgroup$ – Richard Stanley May 23 at 14:24
  • $\begingroup$ @RichardStanley I am unfamiliar with Matroid theory, but from skimming the article (and some related ones) it seems that it is definitely connected to the idea I've presented to some extent, but I don't think it quite captures what I have come up with here. Still, thank you for pointing this out, I suppose I should look into learning some Matroid theory then (recommendations welcome). $\endgroup$ – Justin Benfield May 24 at 5:39

Your Answer

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

Browse other questions tagged or ask your own question.