On the Biplanarity of Blowups

The number of vertices that belong to non-triangular faces in a planar, biplanar, or split thickness two drawing is maximized when the the total excess is distributed among disjoint quadrilateral faces. In this case, the number of such vertices is four times the excess. Any other distribution of the total excess, or non-disjointness among the non-triangular faces, produces fewer such vertices.

Because $G$ is maximal planar, it has excess zero and $3n-6$ edges. Its blowup $2G$ has $2n$ vertices and $12n-24$ edges, four copies of each edge in $G$. Therefore, any biplanar drawing of $G$ has excess $12$, and any split thickness two drawing of $G$ has excess $18$. The number of vertices that can belong to a non-triangular face in these drawings is, respectively, $48$ and $72$. For larger values of $n$, some vertex has triangulated neighborhoods.

As an added vertex in $KG$, $w$ has degree three, so its copy $w_{0}$ in $2KG$ has degree six. To be adjacent to both $v_{0}$ and $v_{1}$, the two images of $w_{0}$ must lie in two triangular faces of the restricted drawing containing $v_{0}$ and $v_{1}$, as shown in Fig. 2. (No face contains both $v_{0}$ and $v_{1}$, because they have triangular neighborhoods and are not adjacent.) This placement limits $w_{0}$ to having as neighbors only the six vertices of these two triangles, matching its degree, so it must be connected to all six of these vertices. The same argument applies to $w_{1}$.

The existence of $w$ in biplanar or split thickness drawings of $2KG$ for graphs with many vertices follows by applying this argument to the vertex $v$ with triangulated neighborhoods given by Lemma 1.

Let $\Delta$ be the triangle of neighbors of $t$ in $H$. $2\Delta$ is isomorphic to $K_{2,2,2}$, the graph of a regular octahedron. We are assuming our drawings have no repeated edges, so two images of $t$ with edge-disjoint neighborhoods in the drawing must come from edge-disjoint triangles of $2\Delta$. Thus, if the four images of $t$ could be drawn with edge-disjoint triangular neighborhoods, these neighborhoods would form four edge-disjoint triangles of $2\Delta$. But in any subdivision of $2\Delta$ into four edge-disjoint triangles (Fig. 3, left), each two triangles share a vertex, and together cover only five vertices of $2\Delta$. If the four images of $t$ were placed in images of these four triangles, the two triangular neighborhoods of $t_{0}$ would miss one of the six neighbors of $t_{0}$ in $2H$, as would the two triangular neighborhoods of $t_{1}$, preventing the drawing from being valid. Therefore, no such drawing is possible.

Suppose for a contradiction that such a drawing existed, and consider the drawings within it of $2K^{2}G$ and of $2KG$. We will find a vertex with triangular neighborhoods in each of these drawings so that the four neighborhoods of the four images of the chosen vertex are nearly disjoint: these neighborhoods can share at most two edges total in $2KG$, at most one edge in $2K^{2}G$, and no edges in $2K^{3}G$. The existence of a vertex in $K^{3}G$ whose triangular neighborhoods share no edges will contradict Lemma 3, showing that no such drawing can exist. To do this, we consider each level of iteration successively, as follows:

• •

  In the drawing of $2KG$, Lemma 2 gives us a vertex $w$ of $KG$ with triangular neighborhoods. The neighborhood of each image of $w$ shares at most one edge with other neighborhoods of images of $w$. For biplanar drawings this is immediate (only one other image is in the same planar subgraph and can share an edge with it). For split thickness two drawings, a neighborhood of $w_{0}$ that shares edges with the neighborhoods of both images of $w_{1}$ is impossible, because then the two images of $w_{1}$ would share a vertex, preventing them from covering all six neighbors of $w_{1}$. Therefore, among the neighborhoods of all four images of $w$, there are at most two shared edges.

• •

  To find a vertex $x$ in $K^{2}G$ with triangular neighborhoods in the drawing of $2K^{2}G$, with at most one edge shared among the neighborhoods of its four images, consider the vertex $w$ found above in $KG$. If the neighborhoods of $w$ have at most one shared edge in the drawing of $2KG$, let $x$ be any neighbor of $w$ added in forming $K^{2}G$ from $KG$. Then $x$ must again have triangular neighborhoods by Lemma 2. Because these triangular neighborhoods must be interior to the triangular neighborhoods of $w$, they can have at most one shared edge (the same edge as the one shared by the neighborhoods of $w$).

  Suppose, on the other hand, that the triangular neighborhoods of $w$ share exactly two edges. Let $\Delta_{0}$, $\Delta_{0}^{\prime}$, $\Delta_{1}$, and $\Delta_{1}^{\prime}$ be the four triangles in $2KG$ neighboring the two images of $w_{0}$ and $w_{1}$, respectively, with an edge shared by $\Delta_{0}$ and $\Delta_{1}$ and another edge shared by $\Delta_{0}^{\prime}$ and $\Delta_{1}^{\prime}$. Because these triangles can only share one edge, and each image of $w$ must be adjacent to images of all three neighbors of $w$, the vertices of $\Delta_{0}$ and $\Delta_{1}$ that are not on the shared edge must be distinct images of the same vertex $u$. Choose a vertex $x$ of $K^{2}G\setminus KG$, adjacent to $w$ and to $u$.

  Because $w$ has triangular neighborhoods in $KG$, its four images in the drawing of $2KG$ are each surrounded by three triangles, formed by images of $w$ and two of its neighbors. For each image, only one of these triangles consists of the three neighbors of $x$. Thus, the four images of $x$ must be placed in these four triangles. Two of these four triangles are subdivisions of $\Delta_{0}$ and $\Delta_{1}$, containing the non-shared images of $u$, and therefore do not share any edge with each other. The only possible shared edge among the triangular neighborhoods of $x$ is the edge shared by $\Delta_{0}^{\prime}$, and $\Delta_{1}^{\prime}$, within which lie the other two images of $x$. Thus, by choosing $x$ in $K^{2}G$ we have eliminated one shared edge between triangular neighborhoods. See Fig. 3, right.

• •

  If the four triangular neighborhoods of $x$ in the drawing of $2K^{2}G$ are edge-disjoint, we already have a contradiction with Lemma 3. Otherwise, we must find a vertex $t$ in $K^{3}G$ whose triangular neighborhoods are edge-disjoint, giving us the desired contradiction. To do so, consider the four triangular neighborhoods of $x$ in the drawing of $2K^{2}G$, only two of which share one edge. For the two triangles that share an edge, the two non-shared vertices of these triangles must be distinct images of the same vertex $y$ in $K^{2}G$. Choose a vertex $t$ of $K^{3}G\setminus K^{2}G$, adjacent to $x$ and to $y$. Then the four triangles in which $z$ must be placed lie within the four triangular neighborhoods of $x$, away from the shared edge of these triangular neighborhoods, so they cannot share any edges with each other. By Lemma 3, this is an impossibility.

We may assume without loss of generality, by triangulating each outerplanar graph if necessary, that both outerpaths are maximal outerplanar: each of their faces is a triangle. If this triangulation step adds two copies of the same edge to the graph, it is not a problem, because the edges added in this triangulation step will be removed from the final drawing.

In each outerpath, the triangular faces form a linear sequence, separated by the internal edges of the outerpath, which are also linearly ordered. In the blowup $2G$, number the two copies of each vertex $v$ as $v_{0}$ and $v_{1}$. If $uv$ is one of the diagonals of one of the outerpaths (that is, one of its internal edges), then $2uv$ is a four-vertex cycle $u_{0}v_{0}u_{1}v_{1}$.

We will construct a biplanar drawing of $2G$ with each plane containing all copies of interior edges of one of the two outerpaths, and two out of the four copies of each boundary edge. We draw copies of the interior edges as nested quadrilaterals, one for each diagonal of its outerpath, in the same order that these diagonals appear within the outerpath. If we draw these quadrilaterals one at a time, from the innermost to the outermost, then each two consecutive quadrilaterals share two opposite vertices, corresponding to the single shared endpoint of the two diagonals.

In each pair of consecutive quadrilaterals, the outer quadrilateral has two potential orientations with respect to the inner one: if the two consecutive diagonals are $uv$ and $vw$, with quadrilateral $u_{0}v_{0}u_{1}v_{1}$ drawn inside quadrilateral $v_{0}w_{0}v_{1}w_{1}$, then these quadrilaterals may be drawn so that pairs $u_{0}w_{0}$ and $u_{1}w_{1}$ are adjacent, or so that pairs $u_{0}w_{1}$ and $u_{1}w_{0}$ are adjacent. In one plane we always choose the orientation with $u_{0}w_{0}$ and $u_{1}w_{1}$ adjacent, and we connect these pairs of vertices by an edge. In the other plane, we always choose the orientation with $u_{0}w_{1}$ and $u_{1}w_{0}$ adjacent, and we connect these pairs of vertices by an edge. In this way, we draw all four copies of each boundary edge, except the edges incident to the two ears (triangles with two boundary edges).

It remains to draw the ears. Each has two boundary edges sharing a vertex, which we call the ear vertex. These two boundary edges have not yet been drawn in the plane of their outerpath. The third edge of the ear is a diagonal whose images form the innermost or outermost quadrilateral in its plane. We place both copies of the ear vertex inside or outside this quadrilateral (respectively as it is innermost or outermost), connected to its two neighbors in the ear with the same numbering convention: in the plane where the quadrilaterals are oriented with $u_{0}w_{0}$ and $u_{1}w_{1}$ adjacent, we connect each ear vertex to neighbors with the same subscript, and in the other plane we connect each ear vertex to neighbors with the opposite subscript.

Thus, all copies of the diagonals of one strip and all copies of boundary edges that connect copies having the same index are drawn in one plane. All copies of the diagonals of the other strip and all copies of boundary edges that connect copies having different indices are drawn in the other plane. The result is a biplanar drawing of the entire blowup $2G$.

From the drawing of Theorem 3.1 for $2G$, add two more edges from the ear vertices to the other vertices on the hexagonal faces they belong to, so that each of the two planes of the drawing contains four images of each triangular face of its outerplanar subgraph of $G$, in two disjoint pairs. These four triangles can be used to place the four images of each added vertex of $KG$.

We may triangulate the faces of $G$, if necessary, preserving the existence of a path–copath decomposition by choosing added diagonals that split each face into an outerpath. As a result, the dual path $P^{*}$ of the path–copath decomposition $(P,P^{*})$ becomes a triangulated outerpath. Each vertex of $G$ may appear multiple times on the boundary of this outerpath, with multiplicity equal to its degree in $P$ (at most two, because $P$ is a path). The outerpath can be formed from $G$ by cutting the plane along each edge of $P$; as a result, each edge of $P$ appears exactly twice on the boundary of the outerpath.

We apply the method of Theorem 3.1 to this single outerpath, producing a drawing in which each appearance of a vertex $v$ of $G$ on the boundary of the outerpath produces images of both copies of $v$. If $v$ appears once on the boundary of the outerpath, its two copies appear once; if $v$ appears twice, its two copies appear twice, giving this drawing split thickness two. This drawing style automatically produces all four images of each edge interior to the outerpath. For an edge $uv$ of path $P$, appearing twice on the boundary of the outerpath, we choose arbitrarily which appearance of $uv$ on the boundary of the outerpath is used to draw edges $u_{0}v_{0}$ and $u_{1}v_{1}$, and which is used to draw edges $u_{0}v_{1}$ and $u_{1}v_{0}$. In this way, all four images of $uv$ are drawn correctly.

Color the vertices of $G$ red, blue, and yellow, and number the copies of each vertex in $kG$ from $0$ to $k-1$. Draw $kG$ as $k^{2}$ disjoint copies of $G$, where for $(i,j)$ with $0\leq i,j<k$ we draw a copy of $G$ consisting of the copies of red vertices numbered $i$, the copies of blue vertices numbered $j$, and the copies of yellow vertices numbered $-(i+j)$ mod $k$. As the disjoint union of $k^{2}$ planar drawings, the result is planar. Each edge of $kG$ appears in one copy of $G$, and each vertex in $kG$ has images in $k$ copies of $G$. As a planar drawing with $k$ images of each vertex, it is a drawing with split thickness $k$.