Do "possible face sets" of planar graphs satisfy the exchange property?

Question

Given a finite planar graph $\mathfrak{G}=(V,E)$, let $Cyc(\mathfrak{G})$ be the set of all cycles in $\mathfrak{G}$. For each planar embedding $f$ of $G$, let $Face(f)$ be the subset of $Cyc(\mathfrak{G})$ consisting of those cycles which become (boundaries of) faces when $\mathfrak{G}$ is embedded via $f$. Based on some general questions which came up when discussing Euler's formula in a graph theory class I just taught, I'm curious about the way cycles do or do not wind up corresponding to faces under a given planar embedding. In particular, the following seems interesting:

Let $f,g$ be planar embeddings of $\mathfrak{G}$, and suppose $\mathcal{A}\subseteq Face(f), \mathcal{B}\subseteq Face(g)$, and $\vert \mathcal{A}\vert<\vert \mathcal{B}\vert$. Must there be a $C\in\mathcal{B}$ such that $\mathcal{A}\cup\{C\}\subseteq Face(h)$ for some planar embedding $h$ of $G$?

Put another way, I'm asking if the family of "possible face sets" of a given planar graph is a matroid. I suspect the answer is negative, but I haven't been able to find a counterexample.

Answer 1

There is one kind of boring way in which the family of possible face sets is not a matroid. Suppose $\mathcal A$ is only almost all of $Face(f)$: one face is left out. Then there is only one remaining face that can be in $Face(f)$: we can deduce its edge set by looking at which edges are not yet part of two cycles in $\mathcal A$. So if $g$ is any embedding that does not include that face, and $\mathcal B = Face(g)$, then nothing from $\mathcal B$ can be added to $\mathcal A$.

But we can also find examples where $\mathcal A$ and $\mathcal B$ are much smaller. Consider the graph $K_{2,5}$, where each of vertices $\{x,y\}$ is connected to each of $\{1,2,3,4,5\}$. It has many possible embeddings, all of which are equivalent to one of the following:

• Put vertices $1, 2, 3,4,5$ on a horizontal line in arbitrary order.
• Place $x$ anywhere above the line and $y$ anywhere below the line.
• Connect all adjacent vertices with straight line segments.

In particular, in an embedding, all face cycles are $4$-cycles of the form $x-i-y-j-x$ where $i,j \in \{1,2,3,4,5\}$, and any such cycle (call it $C_{ij}$) can be a face cycle.

Then take $\mathcal A = \{C_{12}, C_{23}\}$ and $\mathcal B = \{C_{13}, C_{24}, C_{25}\}$. (Here, $\mathcal A$ comes from an embedding $f$ which puts down the horizontal vertices in the order $1,2,3,4,5$, while $\mathcal B$ comes from an embedding which puts them down in order $1,3,4,2,5$, for example.)

Then we cannot add any of $\mathcal B$'s cycles to $\mathcal A$, for the following reason:

• $C_{24}$ and $C_{25}$ both contain the edges $x2$ and $2y$, which are already in both cycles in $\mathcal A$, and no edge can be on three faces.
• If $C_{12}$ and $C_{23}$ are faces, then $C_{13}$ is a cycle with $2$ on one side and $4,5$ on the other side, so it cannot be a face.

By building on this example, we can find ones in which $|\mathcal B| - |\mathcal A|$ is arbitrarily large.