Euler's Formula for 1-planar graphs

Question

Does Euler's Formula hold for 1-planar graphs? I've tested it for a couple of graphs and the result was $3$ instead of $2$.

Given a connected $1$-planar Graph $G=(V,E)$, with $n$ nodes, $e$ edges and $f$ faces. Does the following hold:

$$n - e + f = 3$$

I have not found any literature mentioning Euler's Formula in the context of $1$-planar graphs.

EDIT (copied from one of the comments): "A graph is called $1$-planar if it can be drawn in the plane so that each its edge is crossed by at most one other edge."

Answer 1

Your guess regarding how one might define faces might be useful if you took each pair of points in $G$ that form an overcrossing/undercrossing, and then squish those two points together to form a single new node, thereby converting $G$ into an ordinary planar graph (although changing the count of nodes and edges).

But since you are not squishing those two points together, there's no expectation of any nice formula.

It turns out that there are correct generalizations of Euler's formula, involving some more advanced topology. One such generalization, still comewhat close to Euler's formula for a planar graph, is the Euler characteristic of a surface.

Answer 2

Converting comments to an answer ...

First, we note that the notion of "face" for a $1$-planar graph is problematic. When edges of a $1$-planar graph cross, they create regions that are not surrounded by edges, but rather (at least partially) by "half-edges"; moreover, those regions have "corners" that do not correspond to vertices of the graph. This kind of thing throws-off standard counting arguments. Nevertheless, we can formulate an Euler-like result as follows:

Let $1$-planar graph $G$ have $v$ vertices, $e_0$ non-crossing edges, and $e_1$ crossers. (Note that $e_0$ and $e_1$ are features of a particular drawing of the graph. It may be possible to draw $G$ with fewer (or more) crossing edges.) Define $G'$ as the "apparent" planar counterpart of $G$ based on the particular drawing of $G$.

• "Apparent vertices" are actual vertices, along with edge-crossings (one for every two crossing edges): $$v′=v+\tfrac12 e_1 \tag{1}$$

• "Apparent edges" are non-crossing edges, along with "halves" of the crossing edges: $$e' = e_0+2e_1 \tag{2}$$

• "Apparent faces" are planar regions fully bounded by complete edges (say, $f_0$), along with those that aren't ($f_1$). $$f'=f_0+f_1 \tag{3}$$

Apparent elements satisfy Euler's formula: $$ v'−e'+f'=2 \tag{4}$$ so that we have

$$v−e_0−\tfrac32e_1+f_0+f_1=2 \tag{$\star$}$$

As a sanity check, consider this $1$-planar graph:

(Image credit: David Eppstein, via Wikipedia's "$1$-planar graph" entry.)

Here, we have $v = 14$, $e_0 = 15$, $e_1 = 6$, $f_0 = 0$, $f_1 = 12$, which satisfy $(\star)$.