A Simplified Proof for the Edge-Density of 4-Planar Graphs
September 25, 2025
Abstract
A graph on \(n \ge 3\) vertices drawn in the plane such that each edge is crossed at most four times has at most \(6(n-2)\) edges – this result proven by Ackerman is outstanding in the literature of beyond-planar graphs with regard to its tightness and the structural complexity of the graph class. We provide a much shorter proof while at the same time relaxing the conditions on the graph and its embedding, i.e., allowing multi-edges and non-simple drawings.
1 Introduction↩︎
A drawing \(\Gamma\) of a graph \(G\) is an embedding in the plane such that the vertices are mapped to distinct points and the edges to Jordan arcs connecting the corresponding endpoints. We assume that (i) no vertex is an interior point of an edge, (ii) two edges have only finitely many intersection points, which are either proper crossings or a common endpoint, and (iii) at most two edges cross at a single point. We allow parallel edges and loops in \(G\), if they are non-homotopic in \(\Gamma\), i.e., they form a closed curve with at least one vertex inside and one outside. We denote by \(P(\Gamma)\) the planarization of \(\Gamma\), i.e., the vertices and crossing points of \(\Gamma\) are the vertices of \(P(\Gamma)\), while the edges of \(P(\Gamma)\) are the crossing-free segments in \(\Gamma\), which are bounded by vertices and crossing points.
One of the most important non-planar graph classes is the \(k\)-planar, where each edge can be involved in at most \(k\) crossings. They find direct application in the well-known Crossing Lemma [1]–[3]. For \(k \le 3\) tight (up to a constant) upper bounds on the edge density, i.e., the maximum number of edges a graph \(G\) on \(n\) vertices can have, were shown (\(k=1\): \(4(n-2)\) [4]; \(k=2\): \(5(n-2)\) [3], [5]; \(k=3\): \(5.5(n-2)\) [2], [5], [6]). For \(k=4\), an explicit proof of the tight upper bound \(6(n-2)\) has been given only for the case where \(G\) is simple [7]. Unfortunately, the proof relies on a massive discharging argument with lengthy case analysis. Here, we considerably simplify the proof and extend it to the non-simple case.
Recently, the known upper bound for the edge density of simple 5-planar graphs has been drastically improved from \(\approx 8.3n\) to \(\approx 6.94n\) [8]. A key ingredient for the simplification of the case analysis was a separate treatment of empty triangular faces in the drawing. We apply this idea to the 4-planar setting. For 4-planar graphs, it is known that the upper bound of \(6(n-2)\) can be achieved by a planar hexagonalization where each hexagon \(h\) is enhanced by nine further crossing edges inside \(h\). This hexagonal pattern has been introduced in the past in a more general way [2]. For our purpose, we define an \(F_6^4\) configuration (a full 4-planar hexagon) as an outer-planar drawing of \(K_6 \setminus C_6\), see 2 (a). In the proof of 1, we may assume that an empty triangular face is always part of an \(F_6^4\) ([pro:0-triangle]).
Another source for simplification compared to [7] is the fact that just a few types of faces can exist in \(P(\Gamma)\) ([pro:small-faces] [pro:fill] [pro:cr-minimal] [pro:cr-minimal-2]) – which only holds in our more general setting. This leads to a short proof of the following theorem.
Theorem 1. Any connected 4-planar graph \(G\) on \(n \ge 3\) vertices has at most \(6(n-2)\) edges.
2 Proof of 1↩︎
Proof. Let \(\Gamma\) be a 4-planar drawing of an edge-maximal \(n\)-vertex graph \(G\) that has the maximum number of \(F_6^4\) configurations and is under this condition crossing-minimal.
For a face \(f \in P(\Gamma)\), we define \(\vert f \vert\) as the number of edges and \(v(f)\) as the number of vertices of \(G\) counted while traversing the boundary of \(f\) (so double-counting is possible). We say that \(f\) is a \(v(f)\)-face or, more specifically, a \(v(f)\)-\(\vert f \vert\)-gon and use the terms \(v(f)\)-triangle, \(v(f)\)-quadrilateral and \(v(f)\)-pentagon for the cases of \(\vert f \vert =3,4,5\) respectively. We start by specifying which types of faces can occur in \(P(\Gamma)\).
For that, we prove the theorem by induction on the number of vertices (this is needed for [pro:2-connected]), so observe that for the base case \(n = 3\) at most six non-homotopic edges are possible (three loops and three non-loop-edges). The next proposition is inspired by [7], but we have to adapt it to the non-simple case.
Assume that \(P(\Gamma)\) has a vertex \(x\) that is a crossing in \(\Gamma\) so that \(P(\Gamma) \setminus {x}\) is not connected. Then \(G\) has at most \(6(n-2)\) edges.
Proof. Let \(\tilde{\Gamma}\) be the drawing of the graph \(\tilde{G}\) obtained by adding \(x\) to the vertex set of \(G\). Thus, this adds one vertex and two edges. Let \(\tilde{\Gamma_1}, ..., \tilde{\Gamma_k}\) be the connected components of \(\tilde{\Gamma} \setminus \{x\}\), let \(\Gamma'\) be the drawing induced by the vertices of \(G_1\) and \(x\), and let \(\Gamma''\) be the drawing induced by the vertices of \(G_2 \cup ... \cup G_k\) and \(x\). Let \(G',G''\) be the graphs corresponding to \(\Gamma', \Gamma''\).
By this procedure, no multi-edges of \(G'\) or \(G''\) are homotopic in \(\Gamma'\) or \(\Gamma''\), because the vertex \(x\) separates the same Jordan arcs in \(\Gamma'\) that were separated in \(\Gamma\) by vertices of \(G''\) and vice versa.
Let \(n',n''\) be the number of vertices of \(G',G''\). By construction, we have \(n'+n'' = n+2\ge 5\) and w.l.o.g. \(n' \ge 3\) and \(n''\ge 2\). For \(n''=2\), we observe that \(n=n'\) while \(G'\) has one edge more than \(G\). This contradicts that \(G\) is maximally dense. For \(n'' \ge 3\), we can apply induction and conclude that \(G\) has at most \(6n'-12 + 6n''-12-2 = 6(n+2)-26 \le 6n-12\) edges. ◻
Thus, if the boundary of a face is not a simple cycle, then it is a vertex of \(G\) that appears multiple times.
For each face \(f \in P(\Gamma)\), we have \(\vert f \vert \ge 3\).
Proof. A 0-1-gon implies a self-crossing edge, which is forbidden as the edges are Jordan arcs. A 1-1-gon is created by an homotopic loop and a 2-2-gon by homotopic multi-edges, which both are not allowed. In the case that \(f\) is a 0-2-gon or a 1-2-gon, we have a contradiction to the crossing-minimality of \(\Gamma\) by swapping the two edge-segments forming \(f\). ◻
A face \(f \in P(\Gamma)\) with \(v(f) > 2\) is a 3-triangle.
Proof. Let \(v_1, v_2, v_3\) be the (not necessarily distinct) vertices of \(f\). If \(\vert f \vert \ge 4\), then not all edges \(v_iv_j\) with \(i,j \in \{1,2,3\}\) are present on the boundary of \(f\). Therefore, we can insert such an edge (which is not homotopic to any other edge), contradicting that \(G\) is edge-maximal. ◻
Figure 1: Illustrations for (a)–(b) [pro:cr-minimal] and (c)–(e) [pro:cr-minimal-2]..
A face \(f \in P(\Gamma)\) with \(v(f) = 2\) is a 2-triangle.
Proof. Let \(f\) be a face with vertices \(v_1,v_2\) and assume that \(\vert f \vert \ge 4\). As in the proof above, we can add the planar edge \(v_1v_2\) if not present on the boundary of \(f\) and therefore assume its existence. Let \(e_i\) denote the edges on the boundary of \(f\) starting with \(e_1 = v_1v_2\). Because of \(\vert f \vert \ge 4\), the edge segment of \(e_3\) at \(f\) is not incident to \(v_1\). We can therefore reroute it to be incident to \(v_1\), see 1 (a). While this may introduce a multi-edge or a loop, it can not be homotopic. To see this, assume that \(e_3\) and an edge \(e\) are homotopic in the new drawing. Then, in \(\Gamma\), \(e\) and \(e_3\) must cross and a swapping of their edge-segments between their common vertex and the crossing would yield a drawing with fewer crossings, see 1 (b).
The new drawing has fewer crossings, contradicting the assumption of crossing-minimality (while the number of edges and \(F_6^4\) configurations does not change). ◻
Combining this with [pro:2-connected], we know that the boundary of all faces except 2-triangles and 3-triangles are simple cycles. The non-simple 2-triangles have exactly one vertex on its boundary, which is connected by a loop. There is no need to handle this type separately, as all following arguments work the same for the two types of 2-triangles. Non-simple 3-triangles can be treated the same way.
A face \(f \in P(\Gamma)\) with \(v(f) = 1\) is a 1-triangle or 1-quadrilateral.
Proof. Let \(f\) be a face with vertex \(v\) and assume that \(\vert f \vert \ge 5\). Let \(e_i\) denote the edges on the boundary of \(f\), starting with \(e_1\) incident to \(v\). Then \(e_2\) is not incident to \(v\) at \(f\) and we can reroute it, see 1 (c). While this may introduce a multi-edge or a loop, it can not be homotopic. To see this, assume that \(e_2\) and an edge \(e\) are homotopic in the new drawing. Then, in \(\Gamma\), either \(e_2\) and \(e\) cross in a way that is not crossing-minimal, see 1 (d), or \(e\) has two crossings with \(e_4\) and swapping the edge-segments between the crossings would yield a drawing with fewer crossings, see 1 (e).
The new drawing has fewer crossings and the same number of edges and \(F_6^4\) configurations, thus we found a contradiction to crossing-minimality. ◻
The crucial observation that leads to the simplification of the proof compared to [7] is the next proposition. For that, we define an \(F_6^4\) configuration (a full 4-planar hexagon) as an outer-planar drawing of \(K_6 \setminus C_6\), see 2 (a). This definition is based on the definition of an \(F_p^k\) in [2].
Every 0-triangle \(t \in P(\Gamma)\) is part of an \(F_6^4\) configuration.
Proof. Assume that \(t\) is not part of an \(F_6^4\). Let \(e_1, e_2, e_3 \in G\) be the three edges that form \(t\). These edges are distinct, as self-crossings are forbidden. Let \(v_i, i\in\{1,...,6\}\) be the endpoints of \(e_1,e_2,e_3\), which are not necessarily distinct but nevertheless define a (non-simple), empty hexagon \(h\) as following: Consider all \(v_i\) as different vertices, even if one \(v_i\) may appear multiples times as an endpoint of edges \(e_1, e_2, e_3\). Then we choose an arbitrary tree \(T\) on this six vertices using only edge segments of edges \(e_i\). Such a tree exists as all edge segments of the edges \(e_i\) are connected in \(P(\Gamma)\). Now define \(h\) as the region that closely surrounds \(T\), see 2 (b).
Replace the edges that lie (partially) in \(h\) by an \(F_6^4\) configuration, see 2 (c). All the replaced edges must cross one of \(e_1,e_2,e_3\) and by 4-planarity, there are at most nine of them. Thus, by this procedure we do not lower the number of edges and find a drawing with a larger number of \(F_6^4\) configurations.
Figure 2: (a) A full 4-planar hexagon \(F_6^4\). Dashed edges are not part of the \(F_6^4\) but must exist by [pro:fill]. (b) The three edges forming \(t\) define a (non-simple) hexagon \(h\) (blue) by following closely the edge segments of a tree \(T\) (red) of \(P(\Gamma)\). If \(e_1,e_2\) have a common endpoint \(v\), then they must enclose a further vertex, as otherwise the number of crossings could be reduced. (c) The same vertices and triangle \(t\) after inserting the \(F_6^4\) configuration..
◻
For the main part of the proof, we use the discharging method [7], [9]. First, we assign \(\mathop{\mathrm{ch}}(f) = \vert f \vert + v(f) -4\) charge to the faces of \(P(\Gamma)\), thereby \(4n-8\) charge in total is distributed [10]. Then, we redistribute the charge so that each edge of \(G\) receives at least \(\frac{2}{3}\) and no face in \(P(\Gamma)\) has a negative charge. From this we will conclude that the number of edges in \(G\) is at most \(\frac{4}{2/ 3}(n-2) = 6(n-2)\). More precisely, we will show equivalently that the final charge \(\mathop{\mathrm{ch}}'(f)\) of every face is at least \(\frac{1}{3}v(f)\) and do not transfer the charge explicitly to the edges. Initially, all faces except 0-triangles and 1-triangles have enough charge.
Discharging: We will distribute the charge respecting the property that charge is never moved through planar edges of \(\Gamma\). Therefore, we can study the charge of the faces that lie inside and outside a cycle of planar edges separately. For \(F_6^4\) configurations (which are surrounded by a planar cycle by [pro:fill]), we simply observe that the total charge given and needed both is eight and thus a valid reassigning is possible, see 3.
Figure 3: (a) Initial and (b) redistributed charges in an \(F_6^4\) configuration..
For all faces that are not part of an \(F_6^4\) configuration (which excludes 0-triangles by [pro:0-triangle]), we state explicit discharging rules. Several neighbor-relationships will be helpful: We say that two faces \(f,f'\) are \(i\)-neighbors for \(i \in \{0,1,2\}\) if they share in \(P(\Gamma)\) an edge and \(i\) vertices of \(G\), see 4 (a)). Let \(f_0 \in P(\Gamma)\) be a 1-triangle and \(f_1\) its 0-neighbor. For \(i\ge 1\), if \(f_i\) is a 0-quadrilateral, then let \(f_{i+1}\) be the 0-neighbor of \(f\) at the edge opposite to \(f_{i-1}\). For the maximum \(i\) (which is \(\le 4\) by 4-planarity), we call \(f_i\) the wedge-neighbor of \(f_0\), see 4 (b). The set of all \(f_i\) is the wedge of \(f_0\). Finally, we define two faces \(f,f'\) to be vertex-neighbors, if they share a crossing \(x\) but not an edge of \(P(\Gamma)\) incident to \(x\), see 4 (c).
Figure 4: (Taken from [2].) Illustrations of the defined neighborhood relations. (a) From top to bottom: The faces \(f\) and \(f'\) are 0-neighbors, 1-neighbors, 2-neighbors, respectively. (b) The 0-pentagon \(f_2\) is the wedge-neighbor of the 1-triangle \(f_0\). (c) The faces \(f\) and \(f'\) are vertex-neighbors..
The redistribution of charge takes place in five steps and we denote by \(\mathop{\mathrm{ch}}_i(f)\) the charge of a face \(f\) after the \(i\)-th step, where \(\mathop{\mathrm{ch}}'(f) := \mathop{\mathrm{ch}}_5(f)\) is the final charge. We say a face \(f\) is satisfied after step \(i\), if \(\mathop{\mathrm{ch}}_i(f) \ge \frac{1}{3} v(f)\) and define the excess to be \(\mathop{\mathrm{ch}}_i(f) - \frac{1}{3} v(f)\). The initial charge \(\mathop{\mathrm{ch}}(f)\) is redistributed according to the following steps:
Step 1: Each 1-triangle \(f\) receives \(\frac{1}{9}\) charge from its 1-neighbors that are 2-triangles or 1-quadrilaterals. If the two 1-neighbors of \(f\) are one 2-triangle and one 1-quadrilateral, \(f\) only receives charge from the 2-triangle.
Step 2: Each 1-triangle \(f\) whose 1-neighbors \(f_1,f_2\) are 1-triangles receives \(\frac{1}{18}\) charge from each 1-neighbor of \(f_1,f_2\) that is not \(f\).
Step 3: Each 1-triangle \(f\) receives \(\frac{1}{3} - \mathop{\mathrm{ch}}_2(f)\) charge from its wedge-neighbor.
Step 4: Each face \(f\) distributes its excess equally over all vertex-neighbors that are 0-pentagons.
Step 5: Repeat Step 4.
As in the last two steps only excesses are contributed, it suffices to show \(\mathop{\mathrm{ch}}_3(f) \ge \frac{1}{3} v(f)\). As a preparation, we state some facts about the discharging steps.
Only 2-triangles contribute in Step 2.
Proof. A face \(f\) receiving charge in Step 2 is a 1-triangle with two 1-neighbors \(f_1, f_2\) that are 1-triangles, see 5 (a). Then the statement is a consequence of [pro:fill]. ◻
Figure 5: (a) In Step 2, \(f\) can receive \(\frac{1}{18}\) charge from two 2-triangles each. (b) A 1-triangle \(f\) with a wedge-neighbor that is another 1-triangle causes homotopic edges..
Only 1-quadrilaterals and 0-faces \(f\) with \(\vert f \vert \ge 5\) contribute in Step 3.
Proof. 2-triangles and 3-triangles do not have a 0-edge, which is necessary to be a wedge-neighbor, and 0-quadrilaterals are per definition no wedge-neighbors. It suffices to observe that by [pro:small-faces] [pro:fill] [pro:cr-minimal] [pro:cr-minimal-2] the only other possible face is a 1-triangle, which would imply homotopic multi-edges, see 5 (b). ◻
For all 1-triangles \(f\), we have \(\mathop{\mathrm{ch}}_2(f) \ge \frac{1}{9}\).
Proof. The initial charge of a 1-triangle \(f\) is \(\mathop{\mathrm{ch}}(f) = 0\). 1-triangles do not contribute charge in Step 1 and by [pro:step2], this also holds for Step 2. The 1-neighbors of \(f\) are 1-triangles, 2-triangles or 1-quadrilaterals. So \(f\) receives either at least \(\frac{1}{9}\) charge in Step 1 or \(\frac{1}{18}\) charge from two 2-triangles each in Step 2, which proves the statement. ◻
After Step 3, all faces except 0-pentagons are satisfied. \(0\)-faces \(f\) with \(\vert f \vert \ge 6\) have an excess of at least \(\frac{1}{9}\vert f \vert\) after Step 3.
Proof. Recall that by [pro:small-faces] [pro:fill] [pro:cr-minimal] [pro:cr-minimal-2] only \(0\)-faces, 1-triangles, 1-quadrilaterals, 2-triangles and 3-triangles exist in \(P(\Gamma)\). By assumption, there are no 0-triangles and by [pro:wedge-neighbors] [pro:1-triangle], the statement is true for 1-triangles. For the following analysis, we use [pro:step2] [pro:wedge-neighbors]:
2-triangles \(f\): \(\mathop{\mathrm{ch}}(f)=1\), \(\mathop{\mathrm{ch}}_1(f) \ge 1- \frac{2 \cdot1}{9} = \frac{7}{9}\) and \(\mathop{\mathrm{ch}}_3(f) = \mathop{\mathrm{ch}}_2(f) \ge \frac{7}{9}-\frac{2 \cdot 1}{18} = \frac{6}{9} \ge \frac{1}{3} \cdot 2\).
3-triangles \(f\): \(\mathop{\mathrm{ch}}(f)=2\) and \(\mathop{\mathrm{ch}}_3(f) = 2 \ge \frac{1}{3} \cdot 3\).
0-quadrilaterals \(f\): \(\mathop{\mathrm{ch}}(f)=0\) and \(\mathop{\mathrm{ch}}_3(f) = 0 \ge \frac{1}{3} \cdot 0\).
1-quadrilaterals \(f\): \(\mathop{\mathrm{ch}}(f)=1\) and \(\mathop{\mathrm{ch}}_2(f) = \mathop{\mathrm{ch}}_1(f) \ge 1 - \frac{2\cdot 1}{9} = \frac{7}{9}\). As \(f\) contributes through at most two edges in Step 3, we have \(\mathop{\mathrm{ch}}_3(f) \ge \frac{7}{9}-\frac{2\cdot2}{9} =\frac{3}{9} \ge \frac{1}{3} \cdot 1\).
\(0\)-faces \(f\) with \(\vert f \vert \ge 6\): \(\mathop{\mathrm{ch}}(f) = \vert f \vert -4 = \mathop{\mathrm{ch}}_2(f)\) and \(\mathop{\mathrm{ch}}_3(f) \ge \vert f \vert-4- \frac{2}{9} \vert f \vert\). Thus, \(\mathop{\mathrm{ch}}_3(f) \ge 0 + \frac{1}{9} \vert f \vert\) holds.
◻
After Step 5, all 0-pentagons are satisfied.
Proof. If at most four wedge-neighbors of \(f\) are 1-triangles, then we have \(\mathop{\mathrm{ch}}_3(f) \ge \frac{1}{9}\), so assume that all five wedge-neighbors of \(f\) are 1-triangles, thus \(\mathop{\mathrm{ch}}_3(f) \ge -\frac{1}{9}\). By [pro:easy-faces], \(f\) receives enough charge in Step 4, if a vertex-neighbor is a large 0-face. So assume all vertex-neighbors of \(f\) are 1-triangles, 2-triangles, 0-quadrilaterals, 1-quadrilaterals or 0-pentagons.
We introduce some notation for such 0-pentagons: Let \(e_i \in G\) for \(0 \le i \le 4\) be the edges that form \(f\), let 1-triangle \(t_i\) be the wedge-neighbor of \(f\) at \(e_i\) and denote by \(v_i\) its vertex. Denote the vertex-neighbors of \(f\) at the crossing of \(e_i\) and \(e_{i+1 \mod 5}\) by \(f_i\).
- Case 1: One vertex-neighbor of \(f\) is a 2-triangle. W.l.o.g. let \(f_0\) be a 2-triangle. If \(\mathop{\mathrm{ch}}_3(f_0) \ge \frac{7}{9}\), then \(f_0\) has an excess of \(\frac{1}{9}\) and \(\mathop{\mathrm{ch}}_4(f) \ge 0\). If \(\mathop{\mathrm{ch}}_3(f_0) < \frac{7}{9}\), then \(f_0\) contributes charge in Step 2, implying that w.l.o.g. \(f_4\) is a 1-triangle whose 1-neighbors both are 1-triangles, see 6 (a). Then, by the 4-planarity of \(e_3\), \(f_1\) is also a 2-triangle. So \(\mathop{\mathrm{ch}}_2(t_1) = \frac{2}{9}\) and \(f\) contributes only \(\frac{1}{9}\) charge to \(t_1\) in Step 3. Thus, \(\mathop{\mathrm{ch}}_3(f) \ge 0\).
In the following, we can assume that wedges of all \(t_i\) contain at most one 0-quadrilateral, as otherwise one vertex–neighbor of \(f\) is a 2-triangle and we can refer to Case 1.
Figure 6: Illustrations for (a) Case 1 and (b)–(c) Case 2..
Case 2: One vertex-neighbor of \(f\) is a 1-quadrilateral. W.l.o.g. let \(f_0\) be a 1-quadrilateral.
Case 2.1: The vertex of \(f_0\) is \(v_0\) or \(v_1\). By symmetry, assume that the vertex of \(f_0\) is \(v_0\). Observe that at most two vertex-neighbors of \(f_0\) are possibly 0-pentagons (the third vertex-neighbor is the 1-triangle \(t_1\)). If \(f_0\) does not contribute charge to both its wedge-neighbors, then it has an excess of \(\frac{2}{9}\) after Step 3 and so \(\mathop{\mathrm{ch}}_4(f) \ge 0\). Otherwise, we have the configuration depicted in 6 (b) and \(f\) is the only vertex-neighbor of \(f_0\) that is a 0-pentagon. Here, \(f_0\) does not contribute charge in Step 1 to its 1-neighbor that is not \(t_0\) (if it is a 1-triangle, then another 2-triangle pays). Therefore, \(\mathop{\mathrm{ch}}_3(f_0) = \frac{4}{9}\) and \(f_0\) can contribute its excess of \(\frac{1}{9}\) charge to \(f\) in Step 4.
Case 2.2: The vertex of \(f_0\) is neither \(v_0\) nor \(v_1\). Observe that \(f\) is the only vertex-neighbor of \(f_0\) that is a 0-pentagon. As a second crossing of the wedges of \(t_0,t_1\) would allow a reduction to Case 1, we can assume that the 1-neighbors of \(f_0\) are 2-triangles, see 6 (c). Therefore, \(f_0\) does not contribute charge in Step 1 and has an excess of at least \(\frac{2}{9}\) after Step 3. Thus, \(f\) is satisfied after Step 4.
Case 3: One vertex-neighbor of \(f\) is a 0-quadrilateral. W.l.o.g. let \(f_0\) be a 0-quadrilateral.
Case 3.1: One of \(f_1,f_4\) is a 0-quadrilateral. W.l.o.g. let \(f_1\) be a 0-quadrilateral. Let \(e\) be the edge crossing the wedge of \(t_1\), see 7 (a). As no homotopic multi-edges are allowed, w.l.o.g. the face \(f'\) that is a 1-neighbor of \(t_0\) and a 0-neighbor of \(f_0\) is a 2-face. But \(f'\) can not be a 2-triangle, which is a contradiction to [pro:cr-minimal].
Figure 7: Illustrations for (a) Case 3.1 and (b)–(c) Case 3.2..
Case 3.2: One of \(f_1,f_4\) is a 0-pentagon. W.l.o.g. let \(f_1\) be a 0-pentagon. Observe that if \(f_1\) has a vertex-neighbor \(f'\ne f\) that is a 0-pentagon, then \(\mathop{\mathrm{ch}}_3(f_1) \ge \frac{3}{9}\) and \(f_1\) can contribute enough charge to \(f\) in Step 4, see 7 (b). Otherwise, \(\mathop{\mathrm{ch}}_3(f_1) = \frac{1}{9}\) implies \(\mathop{\mathrm{ch}}_4(f)\ge 0\), and therefore we can assume for the critical case that all wedge-neighbors of \(f_1\) are 1-triangles. Here, only the configuration depicted in 7 (c) exists in that the wedge of \(t_1\) is not crossed twice. In this configuration, \(\mathop{\mathrm{ch}}_3(f_1) = 0\) and \(\mathop{\mathrm{ch}}_4(f_1)\ge \frac{1}{9}\), which is enough for \(f\) in Step 5.
Case 3.3: Both of \(f_1,f_4\) are 1-triangles. Then \(f_2,f_3\) can not be 0-faces. Also, at most one of them is a 1-triangle, as otherwise there would be an edge homotopic to \(e_3\), see 8 (a). Therefore, \(f_2\) or \(f_3\) is a larger face (which must be a 1-quadrilateral by [pro:fill] [pro:cr-minimal] [pro:cr-minimal-2]) and we can refer to Case 2.
Figure 8: Illustrations for (a) Case 3.3 and (b) Case 4..
From now on, we can assume that all vertex-neighbors of \(f\) are 1-triangles and 0-pentagons.
Case 4: One vertex-neighbor of \(f\) is a 1-triangle. W.l.o.g. let \(f_0\) be a 1-triangle so that the vertex of \(f_0\) is \(v_0\). Then \(f_4\) is also a 1-triangle. Further, \(f_1\) and \(f_3\) are 0-pentagons, because otherwise they would be 1-triangles causing edges homotopic to \(e_1\) and \(e_4\). Finally, this implies that \(f_2\) is a 0-pentagon, see 8 (b). As \(f_2\) does not contribute charge to \(f_1, f_3\) in Step 3, we have \(\mathop{\mathrm{ch}}_3(f_2) \ge \frac{3}{9}\). Here, at most three vertex-neighbors of \(f_2\) are 0-pentagons and therefore \(f\) can receive at least \(\frac{1}{9}\) charge in Step 4.
Case 5: All vertex-neighbors of \(f\) are 0-pentagons. For all \(f_i\), again we have \(\mathop{\mathrm{ch}}_3(f_i) \ge \frac{3}{9}\) and \(f\) is satisfied after Step 4.
◻
The combination of [pro:easy-faces] and [pro:0-pentagons] closes the proof of 1. ◻
3 Open questions↩︎
We demonstrated how the case analysis in the original proof by Ackerman [7] can be shortened. So one may ask if the complexity of this proof can be reduced further. Applying the concept of the density formula might help [11]. Further, our method may open up new possibilities to characterize optimal 4-planar graphs. This new approach might provide a path to improving the density bounds also for k-planar graphs for larger \(k \ge5\), and also to better constants in the Crossing Lemma.