3
$\begingroup$

Context: I have a large collection of nonplanar graphs, all of which I know to be projective-planar with representativity (also known as facewidth) exactly 2. I suspect that all of these graphs contain an edge $e$ whose removal makes the graph $G\backslash e$ planar. Graphs containing such an edge are called by various names in the literature, but I'll stick with "nearly planar".

In Obstructions for embedding cubic graphs on the spindle surface, Archdeacon and Bonnington have the following lemma:

Lemma 8.1. A cubic projective-planar graph is nearly planar if and only if it has facewidth at most two.

Now, if the word cubic was dropped from the lemma above, I would be in business. My question, then, is can it be dropped? That is, is it true that "A projective-planar graph is nearly planar if and only if it has facewidth at most two"?

Of course, the natural thing to do is to follow their argument and see if the graph being cubic is necessary. However, this is where I'm struggling. Here is the proof of the lemma in its entirety:

Fiedler et al. have shown the remarkable result that the orientable genus of a graph embedded in the projective-plane with face-width $w\geq 3$ is $\lfloor \frac{w}{2}\rfloor$. Note that the face-width can vary between different projective-plane embeddings, but not by more than one if one embedding has face-width at least three. The result now follows.

From the cited result, we know that the orientable genus of all of our graphs is 1; that is, they are all toroidal [Note that the result in Fielder et al.'s original paper holds for $w=2$ as well]. However, I don't see the connection between this and the property of near-planarity. Any help in understanding or extending this result would be much appreciated!

$\endgroup$

1 Answer 1

2
$\begingroup$

I've found that, unfortunately, the statement "A projective-planar graph is nearly planar if and only if it has facewidth at most two" is not true. Take for example a large (say $10\times 10$) triangulated grid. Identify the top left and bottom right vertices, as well as the top right and bottom left pair. This graph embeds with representativity two in the obvious way, but this graph does not have a single edge whose deletion leaves it planar.

P.S. This is my first question on SE, so I'm unsure of the etiquette in answering my own question. I've gone with this, but please let me know if I should have edited my question or responded with a comment instead.

$\endgroup$
1
  • 2
    $\begingroup$ Self-answers are welcome as long as it is an answer (instead of a comment). $\endgroup$
    – Trebor
    Sep 2, 2022 at 5:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .