Hanani-Tutte for Radial Planarity II

This paper continues work begun in “Hanani-Tutte for Radial Planarity” [16] by the same authors; to make the current paper self-contained we repeat some of the background and terminological exposition from the previous paper.

In a leveled graph every vertex is assigned a level in \(\{1, \ldots , k\}\). A radial drawing visualizes the leveling of the graph by placing the vertices on concentric circles corresponding to the levels of G. Edges must be drawn as radial curves: for any circle concentric with the others, a radial curve intersects the circle at most once. A leveled graph is radial planar if it admits a radial embedding, that is, a radial drawing without crossings. The concept of radial planarity generalizes level planarity [8] in which levels are parallel lines instead of concentric circles (radially-drawn edges are replaced with x-monotone edges).

We previously established the weak Hanani-Tutte theorem for radial planarity: a leveled graph G is radial planar if it has a radial drawing (respecting the leveling) in which every two edges cross an even number of times [16, Theorem 1]. Our main result is the following strengthening of the weak Hanani-Tutte theorem for radial planarity, also generalizing the strong Hanani-Tutte theorem for level-planarity [15]:

Theorem 1

If a leveled graph has a radial drawing in which every two independent edges cross an even number of times, then it has a radial embedding.

The weak variant of a Hanani-Tutte theorem makes the stronger assumption that every two edges cross an even number of times. Often, weak variants lead to stronger conclusions. For example, it is known that if a graph can be drawn in a surface so that every two edges cross evenly, then the graph has an embedding on that surface with the same rotation system, i.e. the cyclic order of ends at each vertex remains the same [7, 20]. This, in a way, is a disadvantage, since it implies that the original drawing is already an embedding, so that weak Hanani-Tutte theorems do not help in finding embeddings. On the other hand, strong Hanani-Tutte theorems are often algorithmic. Theorem 1 yields a very simple algorithm for radial planarity testing (described in Sect. 5) which is based on solving a system of linear equations over \(\mathbb {Z}/2\mathbb {Z}\), see also [22, Sect. 1.4]. Our algorithm runs in time \(O(n^{2\omega })\), where \(n = |V(G)|\) and \(O(n^{\omega })\) is the complexity of multiplication of two square \(n\times n\) matrices. Since our linear system is sparse, it is also possible to use Wiedemann’s randomized algorithm [24], with expected running time \(O(n^4\log ^2{n})\) in our case.

Radial planarity was first studied by Bachmaier et al. [3]. Radial and other layered layouts are a popular visualization tool (see [4, Sect. 11], [9]); early examples of radial graph layouts can be found in the literature on sociometry [19]. Bachmaier et al. [3] showed that radial planarity can be tested, and an embedding can be found, in linear time. Their algorithm is based on a variant of PQ-trees [6] and is rather intricate. It generalizes an earlier linear-time algorithm for level-planarity testing by Jünger and Leipert [18]. Angelini et al. [2] devised recently a conceptually simpler algorithm for radial planarity with running time \(O(n^4)\) (quadratic if the leveling is proper, that is, edges occur between consecutive levels only), by reducing the problem to a tractable case of Simultaneous PQ-ordering [5].

We prove Theorem 1 by ruling out the existence of a minimal counter-example. By the weak Hanani-Tutte theorem [16, Theorem 1] a minimal counter-example must contain a pair of independent edges crossing an odd number of times. Thus, [16, Theorem 1] serves as the base case in our argument (mirroring the development for level-planarity). In place of Theorem 1 we establish a stronger version, Theorem 4, which we discuss in Sect. 4.

We refer the reader to [16, 21,22,23] for more background on the family of Hanani-Tutte theorems, but suffice it to say that strong variants are still rather rare, so we consider the current result as important evidence that Hanani-Tutte is a viable route to graph-drawing questions.

For the purposes of this paper, graphs may have multiple edges, but no loops. An ordered graph \(G = (V,E)\) is a graph whose vertices are equipped with a total order \(v_1< v_2< \cdots < v_n\). We can think of an ordered graph as a special case of a leveled graph, in which every vertex of G is assigned a level, a number in \(\{1, \ldots , k\}\) for some k. The leveling of the vertices induces a weak ordering of the vertices.

For convenience we represent radial drawings as drawings on a (standing) cylinder. Intuitively, imagine placing a cylindrically-shaped mirror in the center of a radial drawing as described in the introduction.^{Footnote 1} The cylinder is \(\mathcal {C}=I \times \mathbb {S}^1\), where I is the unit interval [0, 1] and \(\mathbb {S}^1\) is the unit circle. Thus, a point on the cylinder is a pair (i, s), where \(i\in I\) and \(s\in \mathbb {S}^1\). The projection to I, or \(\mathbb {S}^1\) maps \((i,s)\in \mathcal {C}\) to i, or s. We denote the projection of a point or a subset \(\alpha \) of \(I\times \mathbb {S}^1\) to I by \(I(\alpha )\) and to \(\mathbb {S}^1\) by \(\mathbb {S}^1(\alpha )\). We define a relation to represent relative heights on the standing cylinder model: for \(x,y\in \mathcal {C}\), let \(x\le y\) iff \(I(x)\le I(y)\). This allows us to write \(\min I(X)\) and \(\max I(X)\) as simply \(\min X\) and \(\max X\) (for \(X\subset \mathcal {C}\)), write \(\min X\le x\) to assert that \(\min I(X) \le I(x)\) (for \(x\in \mathcal {C}\)), etc.

The winding number of a closed curve on a cylinder is the number of times the projection to \(\mathbb {S}^1\) of the curve winds around \(\mathbb {S}^1\), i.e., the number of times the projection passes through an arbitrary point of \(\mathbb {S}^1\) in the counterclockwise sense minus the number of times the projection passes through the point in the clockwise sense. A closed curve (or a closed walk in a graph) on a cylinder is essential ^{Footnote 2} if its winding number is odd. A graph drawn on the cylinder is essential if it contains an essential cycle.

A radial drawing \(\mathcal {D}(G)\) of an ordered graph G is a drawing of G on the cylinder in which every edge is radial, that is, its projection to I is injective (it does not “turn back”), and for every pair of vertices \(u<v\) we have \(I(u)< I(v)\). In a radial drawing, an upper (lower) edge at v is an edge incident to v for which \(\min e =v \) (\(\max e = v\)). A vertex v is a sink (source), if v has no upper (lower) edges. To avoid unnecessary complications, we may assume that I(G) is contained in the interior of I. We think of \(\mathcal {D}\) as a function from G (treated as a topological space) to \(\mathcal {C}\). Thus, \(\mathcal {D}(G')\), for \(G'\subseteq G\), is a restriction of G to \(G'\).

The rotation at a vertex in a drawing (on any surface) of a graph is the cyclic, clockwise order of the ends of edges incident to the vertex in the drawing. The rotation system is the set of rotations at all the vertices in the drawing. For radial drawings, we define the upper (lower) rotation at a vertex v to be the linear order of the ends of the upper (lower) edges in the rotation at v, starting with the direction corresponding to the clockwise orientation of \(\mathbb {S}^1\). The rotation at a vertex in a radial drawing is completely determined by its upper and lower rotation. The rotation system of a radial drawing is the set of the upper and lower rotations at all the vertices in the drawing.

For any closed, possibly self-intersecting, curve in the plane (or cylinder), we can two-color the complement of the curve so that connected regions each get one color and crossing the curve switches colors. A point can appear more than once on the curve, and in such cases the color switches if the closed curve is crossed an odd number of times. For example, a plane graph (embedding) can have a face bounded by a closed curve that uses an edge e twice (once in each direction); crossing e means crossing the boundary walk twice, so the two-coloring will have the same color on both sides of e. If the closed curve is non-essential, the region incident to \(1\times \mathbb {S}^1\) and all other regions of the same color form the exterior (which includes the region incident to \(0\times \mathbb {S}^1\)); the remaining regions form the interior of the curve.

Each pair of edges in a graph drawing crosses evenly or oddly according to the parity of the number of crossings between the two edges. A drawing of a graph is even if every pair of edges cross evenly. A drawing of a graph is independently even if every two independent edges in the drawing cross an even number of times; two edges that share an endpoint may cross oddly or evenly.

For any (non-degenerate) continuous deformation of a drawing of G, the parity of the number of crossings between pairs of independent edges changes only when an edge passes through a vertex. We call this event an edge-vertex switch. When an edge e passes through a vertex v, the crossing-parity changes between e and every edge incident to v.

Let us first recall the weak variant of the result that we want to prove.

Theorem 2

(Fulek, Pelsmajer, Schaefer [16, Theorem 1]). If a leveled graph has a radial drawing in which every two edges cross an even number of times, then it has a radial embedding with the same rotation system and leveling.

We need a stronger version of this result that also keeps track of the parity of winding numbers.

Theorem 3

(Fulek, Pelsmajer, Schaefer [16, Theorem 2]). If an ordered graph G has an even radial drawing, then it has a radial embedding with the same ordering, the same rotation system, and so that the winding number parity of every cycle remains the same.

Theorem 2 follows from Theorem 3 using the construction from [15, Sect. 4.2] that was used to reduce level-planarity to x-monotonicity.

3.1 Working with Radial Embeddings and Even Drawings

Given a connected graph G with a rotation system, one can define a facial walk purely combinatorially by following the edges according to the rotation system (see, for example, [17, Sect. 3.2.6]), by traversing consecutive edges at each vertex, in clockwise order.

We need some terminology for embeddings of an ordered graph G with \(v_1< v_2< \ldots < v_n\). The maximum (minimum) of a facial walk W in the radial drawing of G is the maximum (minimum) v that lies on W. A local maximum (local minimum) of a facial walk W is a vertex v on W so that is larger (smaller) than both the previous and subsequent vertices on W. (A vertex v might appear more than once on W; the previous definition implicitly refers to one such appearance.)

Let \(e = uv\) and \(e'=vw\) be two consecutive edges on the facial walk W of a face f in an embedding \(\mathcal {E}(G)\) of G. We call \((e,v,e')\) a wedge at v in f, and we can identify it with a small neighborhood of v in the interior of f. Intuitively, we think of wedges as being the corners of a face. Given an even drawing \(\mathcal {D}(G)\) of G with the same rotation system as in \(\mathcal {E}(G)\), we identify the wedge \((e,v,e')\) with a small neighborhood of v on the left side of W. A point in the complement of W in \(\mathcal {D}(G)\) is in the interior (exterior) of W if it receives the same (opposite) color as a wedge of W when we two-color the complement of W. Note that in an even drawing, all the wedges of W have the same color, and hence, the definition is consistent.

For general (not necessarily facial) walks W, we call \((e,v,e',-)\) and \((e,v,e',+)\) a wedge at v in an oriented walk W, and identify it with a small neighborhood of v on left and right, respectively, side of W. A wedge of an essential walk W in a radial drawing is above W if its color in the two-coloring of the complement of W is the same as the color of the region incident to \(1\times \mathbb {S}^1\), Otherwise, we say the edge is below W; in that case, it has the same color as the region incident to \(0\times \mathbb {S}^1\).

At each sink (source) v, the wedge that contains the region directly above (below) v is called a concave wedge. A facial walk in an even radial drawing is an upper (lower) facial walk if it contains \(1\times \mathbb {S}^1\) (\(0\times \mathbb {S}^1\)) in its interior. An outer facial walk is an upper or lower facial walk; other facial walks are inner facial walks. If a radial embedding of G has only one outer facial walk (and one outer face) then it also has an x-monotone embedding, using the technique described in Sect. 2.

Let C denote a cycle in an even radial drawing. Let e, f and \(e',f'\), respectively, be edges incident to the maximum v and minimum u of C. Let \(<_v\) be the lower rotation at v and let \(<_u\) be the upper rotation at u. Suppose that \(e<_v f\) and suppose that \(e,e',f',f\) (we allow \(e=e'\) or \(f=f'\)) appear in this order along C. Then C is essential if and only if \(f' <_u e'\). See Fig. 1

Lemma 1

The cycle C is essential if and only if the two paths connecting its extreme vertices do so in inverse order.

Theorem 3 preserves the parity of the winding number of cycles in even radial drawings of ordered graphs, but there are examples showing that we cannot hope to do this when the drawings are only independently even. We will make do with a somewhat weaker property:

Essential cycle (ends of path in inverse order at u and v).

Full size image

Given an ordered graph G with a radial drawings \(D_1\) and \(D_2\), we say that \(D_2\) is supported by \(D_1\) if for every essential cycle \(C_2\) in \(D_2\), there is an essential cycle \(C_1\) in \(D_1\) such that \([\min C_1, \max C_1] \subseteq [\min C_2, \max C_2]\).

A radial drawing of an ordered connected graph is weakly essential if every essential cycle in the drawing passes through \(v_1\) or \(v_n\) (the first or the last vertex). With this definition we can state the strengthened version of our main result which we need for the proof.

Theorem 4

Let G be an ordered graph. Suppose that G has an independently even radial drawing. Then G has a radial embedding. Moreover, (i) if the given drawing of G is weakly essential then G has an x-monotone embedding; and (ii) the new embedding is supported by the original drawing.

Theorem 1 follows from Theorem 4 by the construction from [15, Sect. 4.2].

4.1 Working with Independently Even Radial Drawings

Call an edge drawn on \(\mathcal {C}\) bounded if its points lie between its endpoints (with respect to the I-coordinate); that is, \(u< p < v\) for every point p in the interior of edge uv. Call a drawing of G bounded if all edges are bounded.

Lemma 2

If a graph has an (independently) even bounded drawing, then it has an (independently) even radial drawing with the same rotation system.

We often make use of the following fact.

Lemma 3

Let P be a path and let C be an essential cycle, vertex disjoint from P, in an independently even radial drawing of a graph. Then I(P) does not contain I(C).

If two consecutive edges in the rotation at a vertex v cross oddly, we can make them cross evenly by a local redrawing: we “flip” the order of the two edges in the rotation at v, adding a crossing, which makes them cross evenly. For x-monotonicity it is known [15] that if the edges incident to a vertex cannot be made to cross evenly using edge flips, then there must be a connected component H of \(G\setminus \{v,w\}\) satisfying \(v\le \min H < \max H \le w\) or a multi-edge vw, but both cases can be dealt with. An application of the weak Hanani-Tutte theorem for x-monotonicity completes the proof. We want to use the same approach for radial drawings, and we already know that the weak Hanani-Tutte theorem holds for radial drawings. However, for radial drawings there may be a vertex v whose incident edges cannot be made to cross evenly using flips, but no obstacle like H exists. However, a closer look reveals that this can only happen when the vertex v is either the first or the last vertex of the ordered graph. The next lemma helps us deal with this case.

Given an ordered graph G with vertices \(v_1< \ldots <v_n\) without the edge \(v_1v_n\), let \(G'\) denote the ordered graph obtained by removing \(v_1,v_n\), and replacing each edge \(vv_i\) with \(i\in \{1,n\}\) by a “pendant edge” vu where u is a new vertex of degree one, with u is placed in the order before \(v_2\) if \(i=1\) and after \(v_{n-1}\) if \(i=n\) (and otherwise ordered arbitrarily).

Lemma 4

If G is a connected ordered graph with an (independently) even radial drawing \(\mathcal {D}(G)\), then \(G'\) has an (independently) even radial drawing \(\mathcal {D}'(G')\) such that \(\mathcal {D}'(G\setminus \{v_1,v_n\})= \mathcal {D}(G\setminus \{v_1,v_n\})\).

Using Lemma 4 we can establish part (i) of Theorem 4.

Lemma 5

Suppose that G has an independently even radial drawing that is weakly essential. Then G has an x-monotone embedding.

4.2 Components of a Minimal Counterexample

We establish various properties of a minimal counter-example G—first with respect to vertices, then edges—to Theorem 4 given by an independently even radial drawing \(\mathcal {D}(G)\).

Lemma 6

G is connected.

Let v be a vertex and suppose that B is a connected component of \(G\setminus v\) with \(\min B >v\). By Lemma 6, there exists at least one edge from v to a vertex in B.

Lemma 7

Let v be a vertex and B be a connected component of \(G\setminus v\) with \(\min B>v\). Then either \(|V(B)|=1\) (and the vertex of B has just one neighbor, v) or B is essential.

Lemma 8

Let v be a vertex and B be a connected component of \(G\setminus v\) with \(\min B>v\). If B is essential, then \(v=v_1\).

Lemma 9

Suppose that \(v,w\in V\) and B is a connected component of \(V\setminus \{v,w\}\) with \(v < \min B\), \(\max B< w\), and there is at least one edge from B to v and at least one edge from B to w. Then B is essential.

4.3 Proof of Theorem 4

Let G be a minimal counter-example to the theorem given by an independently even radial drawing \(\mathcal {D}(G)\). We already established part (i) of the theorem in Lemma 5. We also know, by Lemma 6, that G is connected.

If the drawing is even, then Theorem 3 gives us a radial embedding of G, and part (ii) of the theorem is satisfied since Theorem 3 maintains the parity of winding numbers of cycles. So there must be two adjacent edges crossing oddly.

Recall that flipping a pair of consecutive edges in an upper or lower rotation at a vertex changes the parity of crossing between the edges.

First, we repeatedly flip pairs of consecutive edges that cross oddly in the upper or lower rotation at a vertex until none remain. Let e, f be an odd pair of minimum distance in the—without loss of generality—upper rotation of a vertex v. Then let g be any edge in the upper rotation between e and f, which must cross both evenly.

Lemma 10

Suppose that in \(\mathcal {D}(G)\) there exist three paths P, Q and \(Q'\) starting at v such that \(\{e,f,g\}\) is the set of first edges on those paths, with \(\min P < v = \min Q = \min Q'\) and \(V(P)\cap V(Q) = V(P)\cap V(Q')=\{v\}\). Then it cannot be that both \(\max Q > \max P\) and \(\max Q'> \max P\).

P, Q, and \(Q'\) from Lemma 10.

Full size image

The proof of Theorem 4 splits into two cases.

Case 1: Assume that \(v \not = v_1,v_n\) . Let \(G_e,G_f\) and \(G_g\) be the (not necessarily distinct) components of \(G\setminus \{v\}\) containing an endpoint of e, f, g respectively. We are interested in showing that one or more of these intersects \(\{u\in V: u<v\}\). For each of \(G_e,G_f\) and \(G_g\), if it does not intersect that region, then by Lemma 7, it must be either (i) a single vertex or (ii) essential. However, case (ii) is impossible, since then \(v_1=v\) by Lemma 8 (contradiction). Suppose that two of them, let’s say \(G_e\) and \(G_f\) are single vertices \(w_e\) and \(w_f\), respectively, with \(w_e>w_f\). Then remove \(w_f\) and the edge \(vw_f\) from G and apply the minimality of G. Thus, we obtain a radial embedding of \(G\setminus w_f\) supported by \(\mathcal {D}(G\setminus w_f)\). We re-insert \(vw_f\) into the obtained embedding of \(G\setminus w_f\) without crossings by drawing the edge \(vw_f\) alongside the longer edge \(vw_e\). Thus, we can assume that at most one of \(G_e,G_f,G_g\) is of type (i) and none is of type (ii), which means that at least one of them must intersect \(\{u\in V: u<v\}\).

Let P be a path from v through e, f, or g, which ends in the region \(I<v\), chosen so as to minimize \(\max P\), see Fig. 2. Let \(w_P\) be its vertex of max I-coordinate. Choose a minimal such P, so that every vertex except its last is in the region \(I\ge v\). Let \(P_1\) be the initial portion of P, from v to \(w_P\), and let \(P_2\) be the later portion of P, from \(w_P\) to the region \(I<v\).

Let H be the subgraph induced by \(\{u\in V: v< u < w_P\}\). Let \(H_2\) be the component of H that intersects \(P_2\) (empty if \(P_2\) has just one edge) and let \(H_e,H_f,H_g\) be the (not necessarily distinct) components of H incident to e, f, g, respectively (empty if the upper endpoint of that edge is in the region \(I>w_P\)). By the choice of P, \(H_2\) is disjoint (and distinct) from each of \(H_e,H_f,H_g\) and there is no edge from \(H_e\cup H_f\cup H_g\) to the region \(I<v\).

Suppose that \(H_e\) is non-empty and that v is the only vertex adjacent to \(H_e\). By Lemmas 7 and 8 \(H_e\) is a single vertex. Then its only incident edge is e and we proceed as follows.

Remove e and its upper endpoint “\(v_e\)” and apply the minimality of G. Thus, we obtain a radial embedding \(\mathcal {E}(G\setminus v_e)\) of \(G\setminus v_e\) that is supported by \(\mathcal {D}(G\setminus v_e)\). If there is an edge in \(G\setminus v_e\) from v to \(w'\) with \(w' \ge w_P\), simply draw e alongside that edge in the obtained embedding. So let’s assume that there is no such edge. Then \(P_1\) contains at least one vertex in the region \(v<I<w_P\). Let \(H_1\) be the component of H that intersects \(P_1\) and let \(H_1'\) be the subgraph induced by \(V(H_1)\cup \{v\}\). By the choice of P, \(H_1\) is not incident to an edge intersecting the region \(I<v\). The radial embedding \(\mathcal {E}(H_1')\) is non-essential because \(I(H_1')\subseteq I(P_2)\), by Lemma 3. Let \(H_1''\) denote the union of \(H_1'\) with all its incident edges (if any) intersecting the region \(I>w_P\). We can draw e alongside the boundary of the lower outer face of \(H_1''\) in \(\mathcal {E}(H_1'')\) so that it is bounded. Hence, we can apply Lemma 2 to re-embed e without crossings (contradiction).

Thus, if \(H_e\) is non-empty then it must be adjacent to vertices other than v, which means vertices in either region \(I<v\) or \(I\ge w_P\), where the former is ruled out due to the choice of P. By similar arguments, \(H_f\) and \(H_g\) have neighbors in \(I\ge w_P\) unless they are empty. Hence, we have the following.

Lemma 11

Every non-empty subgraph \(H_e,H_f\) and \(H_g\) is non-essential and adjacent to a vertex in \(I\ge w_P\). (If \(H_e\) is empty, then \(\max e \ge w_P\), and similarly for \(H_f\) and \(H_g\).)

Without loss of generality we suppose that P goes through e, since otherwise we can redraw near v to flip the relative order of the ends of e, f, g at v so that P ends at the leftmost edge, renaming it e, renaming the middle one g, and the right one f—then flipping if needed we recover the earlier crossing parities between each pair of edges (e, f), (e, g), (f, g).

Consider minimal paths \(P_f\) and \(P_g\) from v, with first edge f and g, respectively, that end in \(\{u: u < v \text { or } u \ge w_P \}\). (These must exist because if \(H_f\) does not have neighbors in \(I \ge w_P\) then \(H_f\) must be empty, which means that f is an edge from v to \(I \ge w_P\) and thus we can let \(P_f\) be f with its endpoints. Likewise for \(H_g\) to get \(P_g\).)

If neither \(P_e\) nor \(P_f\) intersects \(P_1\), then neither intersects P and both end in \(I>w_P\), which contradicts Lemma 10. Thus, we may assume that there exists a path from v through f or g to \(P_1\) which lies in the region \(v\le I \le w_P\). Hence, there exists a cycle through e, v, f or e, v, g which lies in the region \(v\le I \le w_P\).

We choose C so as to minimize \(\max C\) and to be essential if possible. Let w be the vertex with \(w=\max C\). Without loss of generality, we may assume that \(f\in E(C)\). Let \(B_e\) be the component of \(\{u: v<u<w\}\) that is incident to e, and let \(B_e'\) be the graph formed from the union of \(B_e\) and all incident edges (including e) with their endpoints. Define \(B_f,B_f',B_g,B_g'\) similarly, but in the case that the upper endpoint of g is not in the region \(v<I<w\), let \(B_g=\emptyset \) and let \(B_g'\) be just g with its endpoints.

By the choice of C we have \(B_e\cap B_f = B_e \cap B_g = B_f \cap B_g = \emptyset \). None of \(B_e\), \(B_f\) and \(B_g\) is joined by an edge with a vertex \(u<v\) by the choice of P.

First consider the case that C is not essential. Since g crosses every edge of C evenly and g is between e and f near v—which is in the interior of C— the other endpoint of g must be in the interior of C or on C. In the former case, every vertex of \(B_g\) must be in the interior of C because C and \(B_g\) are disjoint so their edges cross evenly. For the same reason \(B_g\) cannot be adjacent to any vertices in the region \(I>w\), so \(V(B_g')\setminus V(B_g)\subseteq \{v,w\}\). By Lemma 11, \(B_g'\) includes w and \(w=w_P\) and \(H_e\) is non-essential, but then \(B_g\) is essential by Lemma 9, a contradiction since \(B_g\subseteq H_g\). Hence the upper endpoint of g is in C. By the choice of C, it must be w; i.e., \(g=vw\). Let \(C'\) be the cycle formed from g and either of the paths from v to w in C. since \(\max C'=\max C\), when we chose C, we could have chosen \(C'\) instead. Then \(C'\) must be non-essential. Thus, the preceding argument all applies with \(C'\) replacing C, implying that \(e=vw\) or \(f=vw\). The multi-edge vw gives either a direct contradiction if you want to think of it that way, or else remove one, apply induction, and redraw it alongside its parallel edge.

Hence, C is essential, and by the choice of C and P, and by Lemma 3 applied to C and \(P_2\) we obtain that \(w_P=w\). Thus, \(B_e=H_e\), \(B_f=H_f\) and \(B_g=H_g\). Suppose that \(g=vw\). The union \(C\cup g\) contains two cycles through g one of which is non-essential in \(\mathcal {D}(G)\), since otherwise C would not be essential by a simple parity argument. By applying the argument in the previous paragraph to the non-essential cycle, it follows that \(B_e=e=vw\) or \(B_f=f=vw\). Then we can remove one of the multi-edges vw and obtain a contradiction with the choice of G. Hence, we assume that \(g\not =vw\). By Lemma 11, \(\mathcal {D}(B_g')\) intersects the region \(I\ge w=w_P\). Furthermore, by Lemmas 9 and 11, \(V(B_g')\not \subseteq V(B)\cup \{\{v,w\}\), so \(\mathcal {D}(B_g')\) intersects the region \(I>w\). By applying Lemmas 9 and 11 to \(B_e\) likewise, the drawing \(\mathcal {D}(B_e')\) also intersects the region \(I>w\), unless \(e=vw\). In what follows we show that the former cannot happen. Then by symmetry the same applies to f, and hence, we obtain a multi-edge vw contradicting the minimality of G, which completes the proof. Let \(Q'\) be a shortest path in \(B_g'\) starting at v with g and ending in the region \(I>w\). By assuming that \(\mathcal {D}(B_e')\) intersects the region \(I>w\), we may let \(Q\subseteq B_e'\setminus v\) be a shortest path in \(B_e'\setminus v\) starting with \(e'\) and ending in the region \(I>w\).

We modify the drawing of e and f near v so that they switch positions in the rotation at v; then g crosses both e and f oddly, e and f cross evenly, and the edge g is between e and f. Furthermore, we modify drawings of edges of C near the vertices of C so that every pair of edges of C cross each other evenly; this will not affect the upper rotation at v. We correct the lower rotation at w so that the first edge on \(P_2\), let’s say \(g'\), is between the edges \(e'\in B_e'\) and \(f'\in B_f'\) on C. Since C is essential, the edge \(g'\) crosses C evenly since \(P_2\) begins and ends below C. Since G is independently even, \(g'\) crosses both \(e'\) and \(f'\) either oddly or evenly. In the next paragraph, we show that the edge \(g'\) crosses \(e'\) oddly.

Let \(C_e\) be a cycle consisting of \(Q'\), the part of C between v and w through \(B_e'\), and a new edge edge from w to the upper endpoint of \(Q'\). For convenience, we can make the new edge drawn radially, such that it crosses its incident edge in \(Q'\) evenly (it cannot cross any other edge of \(C'\)). Then every two edges in \(C_e\) cross evenly except for the pair g, e. Consider the two-coloring of the complement of \(C_e\) in \(\mathcal {C}\). Because the two paths in \(C_e\) from v to w cross each other oddly, the color immediately to the right (left) of e at v will be the same as the color to immediately to the left (right) of \(e'\) at w. By Lemma 1 applied to the essential cycle C, f and g are to the right (left) of e at v if and only if \(f'\) and \(g'\) are to the left (right) of \(e'\) at w. Therefore, the upper wedge at v between e and g will have the same color as the lower wedge between \(e'\) and \(g'\) at w; the latter implies that the end of \(g'\) near w will have have that color as well. The entire region \(I<v\) must have the opposite color as the upper wedge at v, and \(P_2\) has an endpoint in this region. Thus, the two ends of \(P_2\) have different colors. Then \(P_2\) must cross \(C_e\) oddly. Since the drawing of G is independently even, it must be that \(g'\) crosses \(e'\) oddly (Fig. 3).

Applying Lemma 10 upside down.

Full size image

As shown earlier, if \(g'\) crosses \(e'\) oddly then \(g'\) also crosses \(f'\) oddly. Let \(Q\subseteq B_e'\setminus v\) be a shortest path in \(B_e'\setminus v\) starting with \(w,e'\) and ending in the region \(I>w_P\). Then we can apply Lemma 10 upside down: the role of “v” in Lemma 10 is played by w, the role of “P” by Q, “Q” is \(P_2\) and “\(Q'\)” is the part of C between v and w through \(B_f'\) (contradiction). Indeed, \(P_2\) is internally disjoint from both Q and C by the choice of P, and Q is internally disjoint from \(B_f\).

Case 2: Assume that \(v = v_1\) or \(v=v_n\) . We can assume that G does not contain edge \(v_1v_n\), since otherwise \(\mathcal {D}(G)\) is weakly essential by Lemma 3, and we are done by Lemma 5. We can also suppose that only pairs of edges at \(v_1\) or \(v_n\) cross an odd number of times. Otherwise, we end up in the previous case. Turn G into a graph \(G'\) with pendant edges as described in the paragraph preceding Lemma 4; then Lemma 4 implies that \(G'\) has an even drawing, so by Theorem 3 it has a radial embedding. We can redraw pendant edges and identify endpoints to obtain a radial embedding of G, but we need to do this carefully to satisfy part (ii) of the theorem if \(G'\) is essential: We “expose” (see Fig. 4) the maximum vertex of the lower face boundary of \(G'\) so that it remains on the lower face boundary of G (and likewise for the the minimum vertex of the upper face boundary). Any essential cycle C in G not present in \(G'\) passes through \(v_1\) or \(v_n\). In order to satisfy part (ii) we need an essential cycle \(C'\) in the embedding of \(G'\) for which \([\min C',\max C']\subseteq [\min C, \max C]\). However, a lower or upper facial walk of \(G'\) contains such a cycle.

Theorem 1 reduces radial planarity testing to a system of linear equations over \(\mathbb {Z}/2\mathbb {Z}\). For planarity testing, systems like this were first constructed by Wu and Tutte [22, Sect. 1.4.2].

Unlike in the case of x-monotone drawings, two drawings of an edge e with end vertices fixed cannot necessarily be obtained one from another by a continuous deformation during which we keep the drawing of e radial: up to a continuous deformation, two radial drawings of an edge differ by a certain number of (Dehn) twists. We perform a twist of \(e=uv\), \(u<v\) very close to v, i.e., the twist is carried out by removing a small portion \(P_e\) of e such that we have \(w\not \in I(P_e)\), for all vertices w, and reconnecting the severed pieces of e by a curve intersecting every edge \(e'\), s.t. \(I(P_e)\subset I(e')\), exactly once. Observe that with respect to the parity of crossings between edges performing a twist of e close to v equals performing an edge-vertex switch of e with all the vertices \(w<v\) (including those for which \(w<u\)). Hence, the orientation of the twist does not matter, and any twist of e keeping e radial can be simulated by a twist of e very close to v and a set of edge-vertex switches of e with certain vertices w, for which \(u<w<v\).

Exposing \(v_6\) on the lower outer face.

Full size image

By the previous paragraph a linear system for testing radial planarity can be constructed as follows. The system has a variable \(x_{e,v}\) for every edge-vertex switch (e, v) such that \(v\in I(e)\), and a variable \(x_e\) for every edge twist. Given an arbitrary radial drawing of G we denote by \(\mathrm{cro}(e,f)\) the parity of the number of crossings between e and f. In the linear system, for each pair of independent edges \((e,f)=(uv,wz)\), where \(u<v\), \(w<z\), \(u<w\), and \(w<v\), we require

Then G is radial planar if and only if this linear system has a solution.

We conjecture that Theorem 3, and—in light of [14, Sect. 2]—its algorithmic consequences, extend to bounded drawings [13] on a cylinder, defined as follows. We are given a pair \((G,\gamma )\) of a graph G and a map \(\gamma : V \rightarrow \mathbb {N}\), and consider cylindrical drawings of G in which (i) \(u <v\) whenever \(\gamma (u)<\gamma (v)\) for \(u,v\in V\), and (ii) \(\gamma (u)\le \gamma (w)\le \gamma (v)\), where \(uv\in E\) and \(\gamma (u)\le \gamma (v)\), whenever \(I(w)\in I(uv)\). By Lemma 2, radial planarity is the special case in which \(\gamma \) is injective.

In the plane, such a result is already known: a weak Hanani-Tutte variant for bounded embeddings in the plane [12]. (A more general result was proved by M. Skopenkov in a different context [23, Theorem 1.5].) This together with a result showing that edges can be made x-monotone [13, Lemma 1] shows that the corresponding planarity variant coincides with strip planarity [1]. We do not know whether projections of edges to I can be made injective in bounded embeddings on the cylinder, though we conjecture that this is the case.

If the previous conjecture holds, bounded embeddings on the cylinder can be treated as clustered planar embeddings [10, 11] where all the clusters are pairwise nested. The complexity status of this special case of c-planarity is open to the best of our knowledge. The counter-examples in [14, Sect. 6,8], a Hanani-Tutte theorem for this setting would be the most general direct extension of the Hanani-Tutte theorem to clustered planar drawings that we can hope for.