GF(4)-Representations of Bias Matroids of Signed Graphs: The 3-Connected Case

Steven R. Pagano

University of Kentucky

Abstract

Given a signed graph S, we may determine the collection of all fields over which its bias matroid G(S) is representable merely by determining whether G(S) is binary and whether it is GF(4)-representable. We characterize those signed graphs whose respective bias matroids are binary, and we characterize those signed graphs whose bias matroids are GF(4)-representable.

1. Introduction and definitions

A signed graph is a graph with each of its edges labeled “plus” or “minus”. The sign of a path or a circle (i.e., a simple closed path) in a signed graph S is the product of the signs of its edges. The bias matroid G(S) of a signed graph S is the matroid on E(S) whose circuits are the edge sets of S that induce the following types of subgraphs:

i) A positive circle.

ii) A pair of negative circles that meet in exactly one vertex (a “tight handcuff”).

iii) A pair of vertex-disjoint negative circles C₁ and C₂ and a minimal non-self-intersecting path P such that C₁ÈPÈC₂ is connected (a “loose handcuff”).

Zaslavsky (in [10]) gives a construction of a matrix that represents G(S) over all fields of characteristic other than two (in particular, over GF(3)). Because G(S) is ternary, we may apply Whittle’s theorems on ternary matroids [9, Theorems 1.1 and 1.4] and Tutte’s theorem on regular matroids (in [7], [8]) to obtain the following known result:

· If G(S) is binary, then it is representable over all fields.

· If G(S) is GF(4)-representable but not binary, then it is representable over all fields except GF(2).

· If G(S) is not GF(4)-representable, then it is representable over all fields except those of characteristic two.

The entirety of this paper is devoted to proving the following two theorems.

Theorem 1.1. Let S be a 3-connected, simply signed, loopless signed graph which satisfies the non-barrier condition, for which G(S) is nonbinary. Then G(S) is GF(4)-representable iff S is a mesa graph with three negative digons.

Theorem 1.2. Let S be a 3-connected, simply signed, loopless signed graph which satisfies the barrier condition, for which G(S) is nonbinary. Then G(S) is GF(4)-representable iff S is plate-cylindrical.

We shall make use of the following theorem, my main result in [3].

Theorem 1.3. Let S be a connected signed graph, and let be the signed graph obtained by contracting all balanced blocks of S. Then G(S) is binary iff contains no pair of vertex-disjoint negative circles.

We assume the notation and terminology given in Oxley [2] as well as the definitions that follow. In particular, the symbol / denotes contraction, and \ denotes deletion.

A loop is an edge whose endpoints are identical, and a link is an edge with distinct endpoints. A path is said to be trivial if it contains no edges. A graph is said to be empty if it contains no vertices or edges. A pair of paths is said to be internally vertex-disjoint if no vertex internal to one meets the other.

Let X, Y and Z be three subgraphs of a connected graph G for which none of the three is properly contained within another, and for which XÇZ is edge-empty. We say that Y is a barrier between X and Z if all paths connecting X and Z meet a vertex of Y. The relation ~ on E(G)\E(Y) given by

e~f Û Y is not a barrier between e and f

is an equivalence relation. The subgraphs of G induced by the equivalence classes of ~ are called the bridges of Y. A bridge B of Y is trivial if V(B) Í V(Y) and nontrivial otherwise.

We define a vertex cutset of a graph G to be a subset W of V(G) that has two or more nontrivial bridges. A cut-vertex is a vertex v for which {v} is a vertex cutset (as opposed to a cutpoint, which is a vertex with two or more bridges). For a positive integer k, a graph is said to be k-connected if it has no vertex cutsets of size smaller than k. A block of G is a maximal subgraph of G containing no cutpoints. All blocks are 2-connected, and any loop of G is a block in and of itself.

Let X Í E(G) and W Í V(G), both nonempty. By G:X we mean the subgraph of G consisting of X and the endpoints of the edges in X. By G:W we mean the subgraph of G consisting of W and those edges for which both endpoints are contained in W.

Given a graph G, by ±G we mean the signed graph obtained by replacing each edge of G by a pair of signed edges, one positive and one negative. By –G we mean the signed graph obtained from G by replacing each edge of G with a negative edge. By kG we mean the graph obtained from G by replacing each edge of G with k copies of that edge. By S^(k) we mean the signed graph obtained from S by adding a negative loop at each of k distinct vertices, and by S° we mean the signed graph obtained by adding a negative loop to every vertex of S. By C_n we mean the circle with n vertices, and by K_n we mean the complete graph on n vertices. A theta graph is any subdivision of 3K₂.

To switch a vertex of S is to change the sign of all links (i.e., non-loop edges) incident to that vertex. Switching a vertex of S does not change G(S).

A signed graph S is balanced if it contains no negative circles, and unbalanced otherwise. Given a balanced subgraph Y of S, we may switch some subset of V(S) so that all edges of Y are positive (Zaslavsky, [11]). Furthermore, if S is balanced, then G(S) is the cycle matroid of the underlying graph of S, and hence is regular. Zaslavsky also showed [10] that r(S) = |V(S)| – b(S), where b(S) is the number of balanced components of S.

Contracting an edge of S is done as follows:

· If the edge is a positive loop, delete it.

· If the edge is a positive link, then delete it and identify its endpoints.

· If the edge is a negative link, switch one of its endpoints, then delete the edge and identify its endpoints.

· If the edge is a negative loop, delete it and its incident vertex v; all other edges of S incident to v now become negative loops at their other endpoint.

Note that contraction is only defined up to switching.

A signed graph Y obtained from S by a possibly empty sequence of contractions of edges and deletions of edges and/or vertices of S is called a minor of S. Zaslavsky [10] showed that G(S\e) = G(S)\e and G(S/e) = G(S)/e. Given a matroid M, if there is a signed graph S for which M = G(S), then we say that M is signed-graphic.

Finally, we make heavy use of various consequences of Menger’s vertex theorem (see, among others, [1]). Primary among these are the following two theorems:

Theorem 1.4 (Menger). For k ³ 1, a graph G is k-connected iff given any two nonadjacent vertices {v, w} of G there are at least k internally vertex-disjoint paths in G that connect v to w.

Theorem 1.5 (Dirac). If G is a k-connected graph, then whenever V₁ and V₂ are disjoint sets of k vertices, there exist k pairwise vertex-disjoint paths of which each have one endpoint in V₁ and the other endpoint in V₂.

An easy corollary to Theorem 1.5 is the following, which we use most of all:

Corollary 1.6. If G is a k-connected graph and C₁ and C₂ are two vertex-disjoint circles in S with at least k vertices in each, then there exist k pairwise vertex-disjoint paths of which each is internally vertex disjoint from C₁ÈC₂ and has one endpoint in C₁ and the other in C₂.

As stated previously, this paper is dedicated to proving Theorems 1.1 and 1.2. To that end, we first give obtain a forbidden minor lemma (Section 2), then obtain our primary tool for showing when G(S) does have a representation matrix over GF(4) (Section 3). Following that, we discuss mesa graphs and obtain a proof of Theorem 1.1 (Sections 4 and 5), after which we discuss cylindrical and plate-cylindrical signed graphs (Section 6) and obtain a proof to Theorem 1.2 (Sections 7-12).

2. The Forbidden Minors

Theorem 2.1. (Pagano, [4]) G(S) is GF(4) representable iff S does not have any of {±C₃⁽¹⁾, ±C₄\e, –K₄⁽¹⁾} as a minor.

¨

Actually, in this paper, we only need the fact that G(±C₃⁽¹⁾) = F₇^– and G(±C₄\e) = (F₇^–)*, so both ±C₃⁽¹⁾ and ±C₄\e are forbidden minors for GF(4). In fact, we only need consider the following two collections of signed graphs, each of which contain forbidden minors for GF(4).

An evil graph is ±C₄\e or any signed graph that contracts to it.

Let S₁ be obtained by taking +K₄ and adding a negative edge in parallel to each of two nonadjacent edges. If we contract one of the negative edges of S₁, we obtain ±C₃⁽¹⁾, so S₁ is a forbidden minor for GF(4). We call S₁, or any signed graph that contracts to it, a bad drum. The following lemma is immediate from these definitions. It is our primary tool in showing when G(S) is not GF(4) representable.

Lemma 2.2. If S has an evil subgraph or a bad drum minor, then G(S) is not GF(4) representable.

¨

3. Negative Orientations and the w-representation

We now obtain our primary tool in showing when G(S) is GF(4) representable.

A negative orientation of S is obtained by giving a direction to each negative edge of S, so that each negative edge has an initial vertex and a terminal vertex. Given a negative orientation of S, we construct a matrix called an w-matrix of S as follows:

Let J_w be an |V(S)|´|E(S)| matrix over GF(4), with rows indexed by V(S) = {v₁, v₂, …, v_n} and columns indexed by E(S) = {e₁, e₂, … , e_m}. The entries in the row corresponding to e_k are all zero, except possibly for those entries in rows corresponding to endpoints of e_k:

· If e_k = v_iv_i is a loop, then J_w(i, k) is 0 if e_k is positive, and 1 if e_k is negative.

· If e_k = v_iv_j is a positive link, then J_w(i, k) = J_w(j, k) = 1.

· If e_k is a negative link oriented from v_i to v_j, then J_w(i, k) = 1 and J_w(j, k) = w.

An w-representation of S is an w-matrix of S that represents G(S) over GF(4).

We now show that certain negative orientations of S give rise to w-representations of G(S). Given a circle C in S, we choose an arbitrary orientation for C. The negative edges of C are said to be clockwise if their orientation agrees with that of C, and counterclockwise otherwise. (An edge may be clockwise in one circle and counterclockwise in another.) We say that C is compatible provided that C is positive iff the number of clockwise and counterclockwise edges of C are congruent modulo 3. If every circle of C is compatible, then the negative orientation is called a compatible negative orientation (CNO).

Lemma 3.1. If S has a compatible negative orientation, then the w-representation corresponding to that negative orientation represents G(S) over GF(4).

Proof. We need only check that circuits of G(S) map to dependent sets of vectors in J_w, and that bases of G(S) map to independent sets. To this end, we need only prove that a circle maps to a collection of linearly dependent vectors iff it is positive.

Up to row and column permutation, and after deleting all zero rows, the submatrix M of J_w corresponding to a circle in S is

, where .

Now, , which is zero iff the number of a_i’s which are w are congruent modulo 3 to the number of a_i’s which are w+1 iff the number of clockwise and counterclockwise edges of the circle are congruent modulo 3.

¨

We will often show that G(S) is representable over GF(4) by showing that S has a compatible negative orientation.

4. Mesa Graphs

We now introduce our first class of GF(4)-representable signed graphs, and prove one half of Theorem 1.1.

Let S be a connected signed graph with a partition {A, B} of V(S) such that

i) S:A and S:B are both balanced and connected, and

ii) the collection of edges of S with one vertex in A and the other in B induces a subgraph S₀ of S made up entirely of vertex-disjoint negative digons.

We call S a mesa graph. Of particular import is the mesa graph Pr₃ wherein S:A and S:B are both positive triangles and S₀ has three digons.

The following lemma proves one direction of Theorem 1.1.

Lemma 4.1. Let S be a mesa graph with three or fewer negative digons. Then S switches to have a compatible negative orientation, hence G(S) is GF(4) representable.

Proof. We switch S so that S:A and S:B are all positive. We then orient the three negative edges of S from A towards B. This yields a compatible negative orientation for S.

¨

5. The Non-Barrier Case

For this section, we assume that S is 3-connected, loopless, and simply signed.

Lemma 5.1. If S has a Pr₃ minor, then G(S) is GF(4)-representable iff S is a mesa graph with three negative digons.

Proof. Let Y be a subgraph of S that contracts to Pr₃. Then Y is a subdivision of a graph Y¢ obtained by splitting some or none of the vertices of Pr₃. If one of the digons of Pr₃ becomes a 3- or 4-gon in Y¢, then we immediately obtain an evil minor and G(S) is not GF(4)-representable. Thus we assume that Y¢ is the following graph up to switching, and up to the contraction of any edge a_iv_i or b_iw_i.

We choose Y¢ so that the combined lengths of the paths a_iv_i and b_iw_i is a minimum. We let A be the subdivided triangle a₁a₂a₃a₁ in union with the paths a_iv_i and B be the subdivided triangle b₁b₂b₃ in union with the paths b_iw_i. We also let C_i be the subdivided digon supported by v_i and w_i.

Suppose C₁ is not a digon. As S is 3-connected, there must be a path P in S, internally vertex-disjoint from Y, connecting a vertex in C₁\{v₁, w₁} to a vertex in Y\C₁. Let z be the endpoint of P in Y\C₁. If z is on a₁v₁ or b₁w₁, then we obtain an evil subgraph, or we contradict the assumption that the combined lengths of the a_iv_i’s and b_iw_i’s is minimal. If z is anywhere else on Y\C₁, then we obtain an evil subgraph. Thus we may assume that each C_i is a digon.

Suppose there is a path P, internally vertex-disjoint from Y, connecting a vertex y in A to a vertex z in B without using an edge from any C_i. If there is an i for which y is on a_iw_i and z is on b_iw_i, then we contradict the minimality of the lengths of the a_iv_i’s and b_iw_i’s or we contradict the assumption that S is simply signed. If y and z are anywhere else, then we obtain an evil subgraph. Therefore no such path P exists.

Thus ÈC_i is a barrier between A and B. Indeed, ÈC_i has exactly two bridges, A¢ (which contains A) and B¢ (which contains B). To complete the proof, we need only show that A¢ and B¢ are balanced.

Suppose A¢ is unbalanced. Then there exists a negative circle C¢ in A¢. Using Menger’s Theorem (and relabeling if necessary) we obtain a pair of paths P₁ and P₂ in A¢ connecting C¢ to C₁ and C₂ respectively. Let P₃ be any path in B connecting w₁ to w₂. Then C₁ÈP₁ÈC¢ÈP₂ÈC₂ÈP₃ is an evil subgraph of S. Thus A¢ is balanced. Similarly, B¢ is balanced.

¨

We are now able to complete our proof of Theorem 1.1 with the following lemma.

Lemma 5.2. Suppose S satisfies the barrier condition. If G(S) is GF(4)-representable, then S is a mesa graph with three negative digons.

Proof. We show that S has a subgraph Y that contracts to Pr₃.

Let C₁, C₂ and C₃ be vertex-disjoint negative circles in S for which no one is a barrier between the other two. There is a path in S connecting a vertex v₁ in C₁ to a vertex v₂ in C₂ not meeting C₃. There must also be a path connecting C₁ to C₃ and not meeting C₂, so there is a path, internally vertex-disjoint from C₁, C₂, C₃ and v₁v₂, connecting a vertex v₃ on (C₁Èv₁v₂)\v₂ to a vertex v₄ in C₃. Let Y = C₁ÈC₂ÈC₃Èv₁v₂Èv₃v₄.

There is also a path, internally vertex-disjoint from Y, connecting a vertex v₅ on (C₂Èv₁v₂)\v₁ to a vertex v₆ on (C₃Èv₃v₄)\v₃. If this path does not meet C₁, v₁v₂ or v₃v₄, then we have an evil subgraph. Thus we may assume that v₆ is on v₃v₄\v₃. We add v₅ v₆ to Y.

We show that we may assume that v₅ is on C₂\v₂. If not, then among all choices of Y we choose the one such that v₂v₅ has a minimal number of edges. Since v₅ is a not a cut-vertex of S, there is a path, internally vertex-disjoint from Y, connecting a vertex v₇ on (C₂Èv₂v₅)\v₅ to a vertex v₈ in (C₁ÈC₃Èv₁v₅Èv₃v₄Èv₅v₆)\v₅. Regardless of where v₇ and v₈ are, we can replace some portion of Y with v₇v₈ (and relabel appropriately) to obtain either an evil subgraph, a contradiction to the assumption that v₅ is not on C₂, or a contradiction to the assumption that v₂v₅ has a minimal number of edges.

Thus we may assume v₅ is on C₂\v₂. We assume that among all such Y, we have chosen the one such that the length of v₄v₆ is minimal.

Now, v₄ cannot be a cut-vertex, so there is a path in S, internally vertex-disjoint from Y, connecting a vertex v₇ on C₃\v₄ to a vertex v₈ on Y\C₃. We add v₇v₈ to Y. If v₈ is not on v₁v₂, then we either obtain an evil subgraph or contradict the minimality of v₄v₆. We assume that v₈ is on v₁v₂\v₂. Note that, in Y, only v₁v₈ and v₄v₆ may have no edges.

Since S is 3-connected, {v₆, v₈} cannot be a cutset. Thus (up to relabeling) there is a path, internally vertex-disjoint from Y, connecting a vertex v₉ on (C₂Èv₅v₆Èv₂v₈)\{v₆, v₈} to a vertex v₁₀ on (C₃Èv₄v₆Èv₇v₈)\{v₆, v₈}. We add v₉v₁₀ to Y. We obtain an evil subgraph unless both v₉ and v₁₀ are on v₅v₆v₄ or both are on v₂v₈v₇. By the symmetry of Y (including those paths that may or may not be empty), we may assume v₉ is on v₅v₆\v₆ and v₁₀ is on v₄v₆\v₆. Among all such Y we choose the one for which v₅v₉ has minimal length.

Now, {v₅, v₈} cannot be a cutset, so there is a path internally vertex-disjoint from Y connecting a vertex v₁₁ on (C₂Èv₂v₈)\{v₅, v₈} to a vertex v₁₂ on Y\(C₂Èv₂v₈). We add v₁₁v₁₂ to Y, and show that Y contracts to Pr₃.

If v₁₂ is on v₅ v₉, then we at once obtain an evil subgraph or a contradiction to the minimality of v₅v₉. If v₁₂ is not on v₇v₈v₁\v₈ or on v₅v₉, then we obtain an evil subgraph. Thus v₁₂ is on v₇v₈v₁\v₈. If v₁₁ is not on v₂v₈\v₈, then we obtain an evil subgraph.

Let A be the subdivided triangle v₆v₉v₁₀v₆ and B be the subdivided triangle v₈v₁₁v₁₂v₈. It is clear that if A is negative, then Y contains an evil subgraph. Thus A must be positive, and B must also be positive. Thus Y contracts to Pr₃, and we are finished.

¨

6. Cylindrical Embeddings, Plating

We now begin the difficult task of proving Theorem 1.2. In this first section, we make no general assumptions about S.

An embedding of S on an open cylinder S is called cylindrical if, for every circle C of S, C is positive iff C is contractible to a single point. We say that S is cylindrical if it has a cylindrical embedding. The concept of cylindrical embedding is due to some combination of Gerards, Lovász, and Schrijver (see Seymour [6, type (ii) at the top of page 546]).

Suppose we may embed S on S. We may also embed a red line on S which connects the two infinite faces of the embedding, does not meet any vertices of S, and crosses each edge of S a finite number of times. If an embedding of S and the red line can be found such that an edge of S is negative iff the red line crosses it an odd number of times, then we say that S is red-line cylindrical and has a red-line embedding. If we can find a red-line embedding such that each negative edge of S is crossed once by the red line and the positive edges do not meet the red line at all, then we say that S is simply red-line cylindrical and has a simple red-line embedding.

We let S be oriented and we embed the red line on S. Let C be a simple closed curve on S that meets the red line a finite number of times. We choose an orientation for C. A crossing of C with the red line is said to be positive if the orientations of C and S agree at the crossing, and negative otherwise. We define the wrapping number of C to be the number of positive crossings of C minus the number of negative crossings.

Two simple closed curves on S are isotopic if one can be continuously deformed into the other without introducing self-intersections. The following lemma is a standard result from topology.

Lemma 6.1.

a) A simple closed curve C on S has wrapping number in {0, 1, –1}. The wrapping number is 0 iff C is contractible.

b) Ignoring directions of curves, there are exactly two isotopy classes of simple closed curves on S: contractible ones, and ones that wrap around S exactly once.

With this lemma in hand we can prove the following.

Lemma 6.2. The following are equivalent for a connected signed graph S.

a) S is cylindrical.

b) S switches to be red-line cylindrical.

c) S switches to be simply red-line cylindrical.

Proof. By Lemma 6.1, b) Þ a). Clearly c) Þ b). We now show a) Þ c). We assume that S is unbalanced (else the result is trivial).

We begin with a cylindrical embedding of S. Then for some n there is a sequence F₀, F₁, … , F_n of distinct faces of the embedding such that

i) F₀ and F_n are the infinite faces of the embedding, and

ii) For 1 £ i £ n, the boundary of F_i–1 and F_i share at least one edge.

We now draw a red line on S, starting in F₀, and progressing through F₁, F₂, … , F_n, each time passing through one edge a single time to move from one face to the next, never returning to a visited face. Let R be the collection of edges crossed by the red line.

Now, S\R is balanced, as it contains only contractible circles. We switch S\R so that all its edges are positive. Note that S\R is connected, as the red line passes through any face at most once.

Let e Î R. Let P be a path in S\R connecting the endpoints of e. Then PÈe is a contractible circle. Since P is positive, e must be negative. Thus we have switched S so that is simply red-line embedded with respect to our chosen red line.

¨

We need one final concept before beginning our assault on Theorem 1.2. Let V = {a, b, c} be a vertex cutset of a 3-connected signed graph S. Let X be a nontrivial maximal balanced union of bridges of V. Note that no vertex in V is a barrier between the other two in X.

Since X is balanced, the sign of every path in X from a to b is the same sign, which we call s(a, b). We define s(a, c) and s(b, c) similarly. Note that an even number of {s(a, b), s(a, c), s(b, c)} is negative.

Let S¢ be the signed graph obtained from S by deleting X (leaving V in place) and adding edges ab, ac, and bc, with signs s(a, b), s(a, c), and s(b, c) respectively. This new triangle is positive. This operation is called plating, and we say that S¢ is a plating of S. Note that S¢ is also 3-connected and simply signed. Also, the operation of plating decreases the number of vertices in the signed graph. If we perform platings on S until we can no longer perform platings, the resultant graph is called a complete plating of S, and we say that S has been completely plated.

The following lemma is easy but boring, and we leave its proof to the reader.

Lemma 6.3. The operations of switching and plating commute.

¨

If a complete plating of S is cylindrical, then S is plate-cylindrical.

The remainder of this section is given to proving one direction of Theorem 1.2.

Lemma 6.4. If S is cylindrical, then S switches to have a compatible negative orientation, hence G(S) is GF(4)-representable.

Proof. We switch S and then embed S and the red line to obtain a simple red-line embedding of S on the cylinder. We orient the cylinder, and then orient the negative edges of S so that the direction of the crossing of the edge with the red line agrees with the orientation of the cylinder. Let C be a circle in S. If C is positive, then by Lemma 6.1 it has a wrapping number of zero, hence it has an equal number of clockwise and counterclockwise edges. If C is negative, then by Lemma 6.1 its wrapping number is 1 or –1, hence its numbers of clockwise and counterclockwise edges are not congruent modulo three. Thus we have obtained a compatible negative orientation of S, so S is GF(4)-representable.

¨

Lemma 6.5. Let S¢ be a plating of S. If S¢ has a compatible negative orientation, then so does S.

Proof. Let V and X be as in the definition of plating. We take a compatible negative orientation of S¢. The triangle abca is positive. If all three of its edges are positive, then we replace abca by X, with all edges of X positive (we may make this replacement by Lemma 6.3). If exactly two edges of abca, say ab and ac, are negative, then both must point towards a or both point away from a, as S¢ has a compatible negative orientation. We may assume the former. We replace abca by X with all edges of X positive except those incident to a, which are negative. We orient the edges of X to point towards a.

We show that we have obtained a compatible negative orientation for S. Let C be a circle in S. If C contains no path in X, then C is clearly compatibly oriented. Suppose that C contains a path P in X. We may assume that P starts at a and ends at b. Let C¢ be the circle in S¢ obtained by replacing P in C by ab or acb (if P does or does not meet c, respectively). P and the replacement path have the same net difference of clockwise and counterclockwise edges when traveled from a to b. Thus, because C¢ is compatibly oriented, so is C.

¨

From the two preceding lemmas we immediately obtain the following by induction.

Lemma 6.6. If S is plate-cylindrical, then S has a compatible negative orientation, hence G(S) is GF(4)-representable.

¨

Lemma 6.6 proves one direction of Theorem 1.2. We now begin the task of proving the opposite direction.

7. Frames

Throughout the remainder of this chapter, we make the following assumptions about S:

· S is 3-connected, loopless, and simply signed, and satisfies the barrier condition

· G(S) is non-binary and GF(4)-representable.

Our goal is to construct a special subgraph of S, called a frame, and then use this frame to find a canonical embedding of S on the cylinder S. This embedding is given in this section and the following three. Section 3.10 then shows that our embedding is cylindrical, and Section 3.11 deals with what happens when we cannot construct a frame.

Before we begin, recall that a bad drum is the graph +K₄ with a negative edge added in parallel to each of a pair of nonadjacent edges, or a subdivision of this graph. If we change one of the four non-digon edges of the bad drum to negative, then we obtain a good drum. We will call any subdivision of the good drum a good drum as well. Good drums are cylindrical, and so are GF(4)-representable, whereas bad drums are forbidden minors for GF(4).

Let C = {C₁, C₂, … C_n} be a maximal collection of vertex-disjoint negative circles in S. The following lemma follows immediately from the assumption that S satisfies the barrier condition.

Lemma 7.1. We may relabel the circles in C if necessary so that, for any three distinct integers i, j, k in {1, 2, …, n}, C_j is a barrier between C_i and C_k iff either i < j < k or k < j < i.

¨

We assume the labeling guaranteed by Lemma 7.1. Because S is 3-connected and satisfies the barrier condition, none of C₂, … , C_n–1 may be a digon. For the remainder of this section, and for sections 3.7 through 3.10, we assume that neither C₁ nor C_n is a digon, so that we may construct a frame as given below. Section 3.11 concerns those cases wherein we cannot assume that neither C₁ nor C_n is a digon.

Let P_i be a maximal collection of vertex-disjoint minimal paths P for which C_iÈPÈC_i+1 is connected. Note that no path in P_i meets any circles in C other than C_i and C_i+1. By Corollary 1.6, we may assume that |P_i| ³ 3. We call ÈCÈ(ÈP_i) a frame of S with respect to C. The subgraph C_iÈ(ÈP_i)ÈC_i+1 is called the i^th segment of the frame, and the circles in C and the maximal paths in the P_i’s are the struts of the frame. The vertices of the frame are the frame-vertices of S with respect to this frame.

We now show a number of properties of the frame.

We say that v₁, v₂, … , v_n of a circle C_i are in clockwise order if for 1 £ i < j £ n, {v_i, v_j} is a barrier between {v_i+1, … , v_j–1} and {v₁, … , v_i–1}È{v_j+1, … , v_n} (provided neither of these two latter sets is empty). Let P_i = {P₁, P₂, … , P_k}. Let v_i be the endpoint of P_i in C_i and let w_i be the endpoint of P_i in C_i+1. We relabel if necessary to assume that v₁, v₂, … , v_k are in clockwise order on C_i.

Lemma 7.2. The vertices w₁, w₂, … , w_k are in clockwise order on C_i+1.

Proof. If not, S contains a subdivision of the following graph.

v1		v4
w1		w4

Here, v₁v₂, v₂v₃, v₃v₄, w₁w₃, w₃w₂, and w₂w₄ are positive, v₁v₄ and w₁w₄ are negative, and the remaining four edges are of indeterminate sign.

If v₁w₁ and v₃w₃ are of opposite sign, then we delete v₂w₂ and contract v₁v₂ and w₁w₃w₂ to obtain an evil minor. Thus v₁w₁ and v₃w₃ have the same sign. Similarly, v₂w₂ and v₄w₄ have the same sign. Thus our subgraph switches to become the bad drum.

¨

Let P₁, P₂, … , P_k be the paths in P_i in clockwise order. Let R_i,j be the path in C_i between the endpoints of P_j and P_j+1 not meeting any other path in P_i, and R_i+1,j be the path in C_i+1 defined similarly. The subgraph P_jÈP_j+1ÈR_i,jÈR_i+1,j is called a panel frame, and the four vertices of (P_jÈP_j+1)Ç(R_i,jÈR_i+1,j) are the corners of the panel frame.

The next lemma follows immediately from Zaslavsky’s theorem that a balanced subgraph can be switched so that all its edges become positive.

Lemma 7.3. If a path is positive, then we may switch it so that all its edges become positive, without switching terminal vertices of the path. If a path is negative, then we can switch it so that it has a single negative edges, without switching terminal vertices of the path.

¨

Lemma 7.4. We may switch S so that all edges of the frame are positive, except for one negative edge in each circle of C. Furthermore, both negative edges in a segment are contained within a single panel frame of that segment.

Proof. We proceed inductively. We assume that the first i – 1 segments of the frame have been so switched, and show how to switch the i^th without switching vertices in the (i – 1)^th. If i = 1, then we assume that C₁ has been switched so that only one of its edges is negative.

Let v₁, v₂, … , v_k be the endpoints of paths in P_i in C_i and w₁, w₂, … , w_k be the corresponding endpoints in C_i+1. We may assume that the negative edge in C_i is in v_kv₁.

Next, we switch each path in P_i, each time not switching any v_j, so that each edge in the path is positive.

Now, the paths w₁ w₂, w₂ w₃, … , w_k–1w_k are positive, so by Lemma 7.3 we switch vertices not in {w₁, w₂, … w_k} so that each is all positive. We also switch w_kw₁, which is negative, so that it has a single negative edge, without switching w₁ or w_k. We have thus switched C_i+1 without changing the signs of edges in C_i or ÈP_i, so that it has only one negative edge. Note too that the panel frame v₁v_kw_kw₁ contains both negative edges in the first segment of the frame, and no other panel frame in the first segment contains negative edges.

¨

We assume that S has been switched in the manner guaranteed by Lemma 7.3. The panel frames that contain a pair of negative edges are called red, and those with no negative edges are called black. We may switch S so that a given panel frame is red or black. Switching S to move the red panels in this manner is called rotating the frame.

8. Bridges of the Frame

We now wish to make some more assumptions about the frame, and for this we shall need some new definitions. We retain the assumptions made about S in section 7.

Let H be a strut of the frame, and let B be a bridge of H. We call B primary if it meets a frame-vertex not in H. If B is a single edge parallel to and of opposite sign of an edge in H, then B is tertiary. If B is neither primary nor tertiary, then it is secondary.

Lemma 8.1. The frame has at most two tertiary bridges, one at C₁ and the other at C_n.

Proof. Let T be a tertiary bridge of the frame. Then T is an edge of a negative digon D whose other edge e is in the frame. If e is in any path in P_i, then the i^th segment of the frame has an evil subgraph. If e is in C_i (i Ï {1, n}), then {D, C_i–1, C_i+1} violate the barrier condition. Thus e is in C₁ or C_n.

Suppose C₁ has two tertiary bridges T₁ and T₂ with respective corresponding digons D₁ and D₂. If D₁ and D₂ meet then we obtain an evil subgraph. If D₁ and D₂ do not meet, then {D₁, D₂, C₂} violate the barrier condition. This completes the proof.

¨

Let H be a strut of the frame. We define W(H) to be the set of vertices of H which are incident to primary bridges of H.

Lemma 8.2. We may choose a frame without secondary bridges.

Proof. We assume that the number of edges in secondary bridges of circles in C is minimal.

Suppose C_i has at least one secondary bridge. No two vertices of W(C_i) can form a vertex cutset of S. Thus C_i has a secondary bridge B with a path P, internally vertex-disjoint from C_i and with both endpoints in C_i, for which neither of the two paths in C_i connecting the endpoints of P contains all of W_i. We replace C_i in C by the negative circle C_i¢ in PÈC_i containing P. This new C is maximal because S satisfies the barrier condition. Also, C_i¢ has fewer edges in its secondary bridges than C_i did, and no secondary bridges of any other circle in C were otherwise affected. This contradicts our assumption that the number of edges in secondary bridges of our original C is minimal. Thus no circle in C contains a secondary bridge.

We now assume that no circle in C has a secondary bridge. We assume that each P_i has been chosen to have a maximum number of paths. We also assume that we have chosen such a P_i for which the number of edges in secondary bridges of these paths is minimal.

Suppose P_j in P_i has a secondary bridge. No two vertices of W(P_j) can form a vertex cutset of S, so P_j has a secondary bridge B with a path P, internally vertex-disjoint from P_j and with both endpoints in P_j, for which the endpoints of P are a barrier in P_j between a vertex w of W(P_j) and the endpoints of P_j. We replace P_j in P_i by the path P_j¢ in P_jÈP that connects the endpoints of P_j and contains P. But P_j¢ has fewer edges in secondary bridges than P_j did, and no other secondary bridges of the frame have been otherwise affected, and the number of paths in P_i remains a maximum. This contradicts the assumption of minimality of the number of edges in secondary bridges of paths in P_i. Thus no path in P_i has a secondary bridge. This completes the proof.

¨

The need for these two lemmas will become apparent in the next section.

9. Panels

We recall previous assumptions about S and the frame, and add a few new assumptions to obtain the following list, which we will retain throughout this section and the following two.

· S is 3-connected, loopless, and simply signed, and satisfies the barrier condition.

· G(S) is non-binary but GF(4)-representable.

· C has no digons, and we have constructed a frame with respect to C.

· The frame has been switched so that all its edges are positive, save for one negative edge in each circle in C.

We now need the following rather technical lemma.

Lemma 9.1. Let P_i in P_j = {P₁, P₂, … P_k} have endpoints a_i in C_j and b_i in C_j+1, where P_i is adjacent to P_i–1 and P_i+1 modulo k for each i. Then S cannot have four vertices {w, x, y, z} such that

· x and y are on C_j\a₂,

· w is on P₂\a₂,

· x, y and w are not all in the same panel frame,

· z is not a frame vertex, and there are three pairwise internally disjoint paths, each of which is internally disjoint from the frame, which respectively connect z to x, y, and w.

Proof. Suppose x, y, w, and z are as in the statement of the lemma. We may assume that C_j has been switched so that its negative edge e is on the path in C_j connecting x to y and not meeting a₂. Suppose y is not on a₁a₂a₃. We may assume that {e, a₃} is a barrier between y and {x, a1, a₂}. If yzw is positive, then C_jÈC_j+1ÈP₂ÈP₃Èywz is evil. If yzw is negative, then C_jÈC_j+1ÈP₂ÈP₁Èywz is evil. Thus y (and similarly x) must be on a₁a₂a₃.

So we now assume that x is on a₁a₂\a₂ and y is on a₂a₃\a₂. We also assume that neither panel frame containing w is red. We choose {w, x, y, z} so that the combined lengths of xa₁, ya₃, and wb₂ are minimal.

Let Y₁ be the Y-graph on {w, x, y, z} and Y₂ be the Y-graph on {w, x, y, a₂}. Let Y = C_jÈC_j+1È(ÈP_j)ÈY₁. If Y₁ÈY₂ is unbalanced then Y has an evil subgraph. Thus we assume that each edge of Y₁ is positive.

Suppose {w, x, y} separates Y₁ÈY₂ from the rest of the frame in S. Let B be the union of bridges of {w, x, y} that contain Y₁ or Y₂. B is a block because S is 3-connected. B cannot be balanced, else it would have been plated out. Thus B contains a negative path which is internally vertex-disjoint from Y₁ÈY₂ and connects a pair of vertices of Y₁ÈY₂, not both in {w, x, y}. Regardless of the sign of the path and the placement of its endpoints, we obtain an evil minor.

Thus {w, x, y} does not separate Y₁ÈY₂ from the rest of the frame in S. Thus there must be a path in S, internally vertex-disjoint from Y, connecting a vertex v₁ in (Y₁ÈY₂)\{w, x, y} to a frame vertex v₂ not in Y₁ÈY₂. Because Y₁ and Y₂ are interchangeable in the frame, we assume v₁ is on Y₁.

If v₂ is not in the j^th segment of the frame, then we violate the barrier condition. If v₂ is not in one of the two panels in the j^th segment containing w then we replace zw by v₁v₂ and relabel to obtain a previous contradiction. If v₂ is on any of xa₁, ya₃, or wb₂, then we contradict the minimality of the lengths of these three paths. We may thus assume that v₂ is on the interior of a₁b₁b₂. Let P be the path in Y₁Èv₁v₂ that connects y and v₂, and let Y¢ = C_jÈC_j+1ÈP₁ÈP₂ÈP₃ÈP. If P is positive, then Y¢ is a bad drum. If P is negative, then Y¢ contains an evil subgraph. This completes the proof.

¨

A frame-chordal path in S is a path that is internally vertex-disjoint from the frame and connects two frame-vertices. Thus all edges of S not in the frame are contained in frame-chordal paths. A frame-chordal path is called proper if it does not have both its endpoints in the same strut.

Let B be a bridge of the entire frame (not simply a bridge of a strut). We say that S is panelable if every such B has all its frame-vertices within a single unique panel frame. We say that B is associated with this panel frame.

Lemma 9.2. Suppose S is completely plated, and our frame has no secondary bridges. Then S is panelable.

Proof. Suppose the frame has a proper frame-chordal path P with endpoints x and y. Now, x and y must belong to the same segment. We at once obtain an evil minor, a bad drum, or a contradiction to the maximality of the P_i’s unless both x and y are in the same circle C_j.

Since P cannot be part of a secondary bridge, there must be a path, internally vertex-disjoint from the frame and P, connecting a vertex z on the interior of P to a vertex w in (without loss of generality) (C_j+1È(ÈP_j))\C_j. If w is in a path in P_j then we contradict Lemma 9.1. Me may thus assume that w and x are not in the same panel frame. But then the proper frame-chordal path xzw gives the same contradiction that P gave in the previous paragraph.

¨

Suppose S is panelable. We define a panel of the S with respect to the frame to be a panel frame in union with all its associated frame-bridges. Thus every non-frame edge of S belongs to a unique panel of S. Non-frame edges and vertices of a panel are said to be interior to that panel. Panels are red or black if their respective panel frames are red or black. We will generally use Q or Q_i to denote panels.

Lemma 9.3. Suppose S is panelable and our frame has no secondary bridges. Let Q be a panel, and let Q¢ be obtained by deleting any tertiary bridges of Q. Then Q¢ is balanced. Furthermore, we can switch non-frame vertices of S so that all black panels have only positive edges.

Proof. We assume (by rotating the frame if necessary) that Q is black. Suppose Q¢ is unbalanced. Then, because S is 3-connected, Q¢ contains a frame-chordal path xy that is negative. We at once obtain an evil minor or bad drum in S unless both x and y are on the same C_j. In this case, since xy cannot be part of a secondary or tertiary bridge, Q¢ has a path internally vertex-disjoint from xy and the frame of Q that connects a vertex z on the interior of xy to a vertex w on the frame of Q but not in C_j. But then one of xwz, ywz is a negative frame-chordal path not having both its edges in the same circle in the frame, and we noted previously that this gives a contradiction. Thus Q¢ is balanced.

Thus we may switch some subset W of V(Q¢) so that Q¢ becomes all positive. Since the frame of Q¢ is already all-positive, we may assume that W contains no frame-vertices of Q¢.

¨

10. Embedding the Panels (Spiderization)

We now work towards obtaining a special planar embedding of the panels of S that we can extend to obtain an embedding on the cylinder S of all of S. This is by far the most difficult and technical section of this work. We retain the assumptions of Section 9. The underlying graph of a signed graph S is denoted |S|.

Let Q be a panel of S. By rotation of the frame we may assume that Q is black. To |Q| we add a vertex z₀, not in S, called a spider vertex, and one edge connecting this spider vertex to each of the four corners of the panel. The resulting unsigned graph Q₀ we call the spiderization of Q. If Q₀ is planar, then we say that Q is spider-planar.

Lemma 10.1. Suppose that S is panelable and our frame has so secondary bridges. If every panel of S is spider-planar, then we may embed |S| on the cylinder S.

Proof. We only need to show that a panel Q can be embedded in the plane so that its frame is the border of the infinite face of the embedding. Tertiary bridges are parallel to edges of the frame, so we may ignore them.

Let Q₀ be the spiderization of Q. We take an embedding of Q₀ on the sphere. The frame of Q partitions the sphere into two regions, one of which contains z₀. Let B be any non-tertiary bridge of the frame of Q in Q. B cannot be secondary, so it contains vertices in two strictly different sides of the frame. Thus B must be embedded in the region of the sphere not containing z₀. Thus Q₀\z₀ has been embedded with the panel frame bordering one face of the embedding. This completes the proof.

¨

The next series of lemmas culminates in showing that every panel of S is indeed spider-planar. Recall that if S is completely plated and our frame has no secondary bridges, then S is panelable and panels are well-defined.

Lemma 10.2. Suppose that S is completely plated and our frame has no secondary bridges. Let Q be any panel, and let Q₀ be the spiderization of Q with all its non-corner degree-two vertices suppressed. Then Q₀ is 3-connected.

Proof. Let W = {v, w} be a cutset of Q₀. Then W has at least two nontrivial bridges in Q₀.

Suppose v is not a frame-vertex, and let B be a bridge of W in Q₀ not containing frame-edges. Then W separates B from the frame in S, a contradiction. Therefore both v and w are frame-vertices.

If v and w are not on the same side of the panel frame, then W separates a nontrivial bridge B from the frame again. So, suppose v and w are on the same side of the panel frame, and let B be a nontrivial bridge of W not containing corner vertices other than those in W. Then B is a path or it contains a secondary bridge, both of which are contradictions.

¨

Lemma 10.2 at once gives us the following as a corollary:

Lemma 10.3. Suppose that S is completely plated and our frame has no secondary bridges. Then every panel of S is 2-connected.

¨

The next lemma is a primary tool in finding forbidden subgraphs.

Lemma 10.4. Suppose that S is completely plated and our frame has no secondary bridges. Let Q be a panel of S with respect to this frame. Let a, b, c, d be four vertices in clockwise order on the frame of Q, not all on the same side of the frame. Then there cannot be a pair of vertex-disjoint frame-chordal paths in Q, the first one (called R₁) connecting a to c, and the second (R₂) connecting b to d.

Proof. We assume Q is black and switched to be all positive. Let Y be the frame of Q in union with R₁ and R₂. We may assume that Q abuts C₁ and C₂. Let s₁, s₂, t₁, t₂ be the corners of Q in clockwise order, with s_i on C₁ and t_i on C₂. We immediately obtain a bad drum or a contradiction to the maximality of P₁ unless (up to relabeling) one of the following cases occurs:

1) t₂abs₁cds₂ is a path in the frame of Q, b ¹ s₁ ¹ c;

2) s₁abcs₂ is a path in the frame of Q and d is on the interior of s₁t₂;

3) t₂abcs₁ is a path in the frame of Q and d is on the interior of s₁s₂t₁.

Case 1. We replace s₁t₂ in P₁ by cat₂ to obtain a contradiction to Lemma 9.1.

Case 2. We assume that the combined length of s₁a and cs₂ is minimal. R₁ is not a secondary bridge, so there is a path v₁v₂, internally vertex-disjoint from Y, connecting a vertex v₁ on the interior of R₁ to a vertex v₂ on Y\abc. If v₂ is on R₂\b, then we replace the path s₁t₂ in P₁ by the path bdt₂ to obtain a contradiction to Lemma 9.1. If v₂ is on s₁a or bs₂, we contradict the minimality of the lengths of those paths. If v₂ is on the interior of s₂t₁t₂ then we obtain a bad drum. If v₂ is on s₁t₂\{s₁, d} then we reduce to Case 1.

Case 3. We assume that the combined length of t₂a and cs₁ is minimal. Again, R₁ is not a secondary bridge, so there is a path v₁v₂, internally vertex-disjoint from Y, connecting a vertex v₁ on the interior of R₁ to a vertex v₂ in Y\abc. We obtain contradictions similar to those of the previous case unless v₂ is on R₂\b. In this case, we replace s₁s₂ in C₁ by s₁cv₁v₂ds₂, and we replace s₁t₂ and t₁s₂ in P₁ respectively by v₁at₂ and t₁d(s₂) to obtain a contradiction to Lemma 9.1.

¨

The following result of Seymour is of vital importance. For it, we need some special notation. For a graph G, let A be a subset of V(G); we define DA to be the set of vertices in V(G)\A which are adjacent to at least one vertex in A.

Theorem 10.5 (Seymour, [5, 4.1]). Let s₁, t₁, s₂, t₂ be distinct vertices of a graph G = (V, E). Then just one of the following is true:

i) There is a pair of vertex-disjoint paths in G, one connecting s₁ to t₁ and the other connecting s₂ to t₂.

ii) For some k ³ 0, there are pairwise disjoint sets A₁, …, A_k Í V\{s₁, t₁, s₂, t₂} such that

a) for i ¹ j, (DA_i)ÇA_j = Æ,

b) for 1 £ i £ k, |DA_i| £ 3, and

if G¢ is the graph obtained from G by (for each i) deleting A_i and adding new edges joining every pair of distinct vertices in DA_i, and for j = 1, 2 adding an edge e_j joining s_j to t_j, then G¢ can be drawn in the plane with no pairs of edges crossing except e₁ and e₂, which cross exactly once.

¨

We aim towards a reformulation of Seymour’s theorem, with the idea that we wish to show that each panel is spider-planar. We start with the following definitions.

Let G be a graph with four distinct vertices arranged in pairs {s₁, t₁} and {s₂, t₂}. Let W Í V(G) be a vertex cutset of G of size three or less, and let {B₁, B₂, … , B_m} be the collection of nontrivial bridges of W which contain no vertices in {s₁, s₂, t₁, t₂}\W. Let B be a nonempty union of the B_i’s. We call B a special plate of W with respect to this choice of {{s₁, t₁}, {s₂, t₂}}. A special plate is maximal if it is the union of all the B_i’s. By a special plating of G by W we mean the operation of deleting B and, for every pair of vertices in W, adding an edge between those vertices. If we perform special platings on G until no more special platings can be performed, we obtain a complete special plating of G. We now spiderize G by adding a vertex z₀ and edges z₀s₁, z₀s₂, z₀t₁, and z₀t₂. If a complete special plating of G is spider-planar, then we say that G is plate-spider-planar with respect to {{s₁, t₁}, {s₂, t₂}}.

Lemma 10.5a. In S, the operations of spiderization and special plating commute.

Proof. Immediate from the fact that special plating does nothing to the corners, and from the observation that z₀ cannot be part of W.

¨

Lemma 10.5b. Suppose S is completely plated and our frame has no secondary bridges. Let Q be a panel of S with its non-corner degree-two vertices suppressed, and corners s₁, s₂, t₁, t₂ in clockwise order. Let B be a special plate of Q with respect to its corners. Then |W| = 3. Furthermore, W contains a pair of frame-vertices on the same side of Q, and the other vertex in W is not on the same side as the first two.

Proof. Recall that Q is 2-connected. As in the proof of 10.2, if |W| = 2 then B is a secondary bridge of the frame or W is a cutset in S, both of which are impossible. Thus |W| = 3.

If B does not contain a frame vertex other than those in W, then W separates B from the frame in S, contradicting the assumption that S is completely plated. Thus W contains a pair of vertices on the same side of Q. If the final vertex of W is on the same side, then B is a secondary bridge, a contradiction.

¨

Lemma 10.6. Suppose that S is completely plated and our frame has no secondary bridges. Let Q be a panel of S with corners s₁, s₂, t₁, t₂ in clockwise order, with the non-corner degree-two vertices of Q suppressed. Let Q¢ be a complete special plating of Q with respect to {{s₁, t₁}, {s₂, t₂}}. There are vertex-disjoint paths P₁and P₂ in Q that connect s₁ to t₁ and s₂ to t₂ respectively iff there are vertex-disjoint paths P₁¢ and P₂¢ in Q¢ that connect s₁ to t₁ and s₂ to t₂ respectively.

Proof. We may assume Q¢ is obtained by a single special plating of Q, replacing B by X.

By Lemma 10.5b, |W| = 3.

Suppose P₁ and P₂ exist. At most one can contain edges of B. If neither contain edges of B, there is nothing to prove. If P₁ contains edges of B, then let P₂¢ = P₂ and we replace P₁ÇB in P₁ by a corresponding path in X, starting and ending at the endpoints of P₁ÇB and meeting another vertex in W iff P₁ meets that vertex.

Conversely, if P₁¢ and P₂¢ exist, then at most one contains edges in X. If P₁¢ contains edges of B, we let P₂ = P₂¢ and replace P₁¢ÈX by a path in B that starts and ends at the endpoints of P₁¢ and meets the other vertex of W iff P₁¢ does.

¨

We are now ready to give a reformulation of Seymour in our special case.

Lemma 10.7. Suppose S is completely plated and our frame has no secondary bridges. Let Q be a panel of S with corners s₁, s₂, t₁, t₂ in clockwise order, with its non-corner degree-two vertices suppressed. Then exactly one of the following is true.

1) There are vertex-disjoint paths P₁ and P₂ in Q such that P_i connects s_i to t_i.

2) Q is plate-spider-planar with respect to {{s₁, t₁}, {s₂, t₂}}.

Proof. Let Q₀¢ be a complete special plating of the spiderization Q₀ of Q. By 10.5a, Q₀¢ is a spiderization of a complete special plating Q¢ of Q.

Let Q* be obtained from Q by adding edges e₁ = s₁t₁ and e₂= s₂t₂. It is clear that Q₀ is planar iff Q* can be drawn in the plane so that only the edges e₁ and e₂ cross (we exchange the e_i’s and the crossing with the edges z_is_i and z_it_i and z₀). The equivalent holds for Q₀¢ and Q₀*.

If 1) holds, then by Lemma 10.6, there are vertex-disjoint paths P₁¢ and P₂¢ in Q¢ connecting s₁ to s₂ and t₁ to t₂ respectively. Thus by Theorem 10.5 Q₀* cannot be drawn in the plane such that the only crossing is that of e₁ and e₂, so Q₀¢ is not planar. Thus Q is not plate-spider-planar.

If 1) fails, then the paths do not exist in Q¢. Thus Q₀¢ is planar, and Q is plate-spider-planar.

¨

We now move towards the final result of this section.

Lemma 10.8. Suppose S is completely plated and our frame has no vertices. Let Q be a panel of S. Then Q is spider-planar iff Q is plate-spider-planar.

Proof. We may assume that we have suppressed all non-corner degree-two vertices of Q. We may also assume that Q¢ is obtained from Q by a single special plating, replacing B by X via W = {a, b, c}. By 10.5a, we may assume that a and b are on the same side S of Q. Since W separates B from the rest of Q but B is not a secondary bridge of the frame, there is a path that is internally vertex-disjoint from B and the frame of Q that connects c to a vertex frame-vertex d of Q not on S. Also, W cannot separate B from the rest of frame in S, B contains a frame vertex x on the interior of ab.

We show that B is plate-spider-planar with respect to a, c, b, x. Any special plating of B is a special plating of Q, so B cannot be special-plated. If B is not spider-planar with respect to {{a, b}, {c, x}}, then BÈcd contains paths R₁ and R₂ that contradict Lemma 10.4. Thus B is plate-spider-planar with respect to {{a, b}, {c, x}}.

B is also 2-connected because it is minimal. Thus there are internally vertex-disjoint paths in B, one connecting c to a and the other connecting c to b. Because B contains no secondary bridges and no cutpoints, we may assume that these paths meet S only at a and b respectively. Thus B contains a circle C with a, c, b, x in clockwise order. Using arguments similar to those in Lemmas 8.2 and 10.1, we may assume C is such that B can be embedded in the plane so that C borders the infinite face of the embedding.

Now, C is a subdivision of X. Thus, by the last sentence of the previous paragraph, Q is spider-planar with respect to {{s₁, t₁}, {s₂, t₂}} iff Q¢ is.

¨

The following is immediate from Lemmas 10.7 and 10.8.

Corollary 10.9. Suppose S is completely plated and our frame has no secondary bridges. Let Q be a panel of S with corners s₁, s₂, t₁, t₂ in clockwise order, with its non-corner degree-two vertices suppressed. Then the following are equivalent.

1. There are not vertex-disjoint paths P₁ and P₂ in Q such that P_i connects s_i to t_i.

2. Q is plate-spider-planar with respect to {{s₁, t₁}, {s₂, t₂}}.

3. Q is spider-planar with respect to {{s₁, t₁}, {s₂, t₂}}.

¨

From Lemmas 10.4 and Corollary 10.9, we obtain the following.

Lemma 10.10. Suppose that S is completely plated and our frame has been constructed without secondary bridges. Then every panel of S is spider-planar.

Proof. Let Q be a panel of S. We may suppress all non-corner degree-two vertices when trying to determine whether Q is spider-planar, so we do so.

If Q is not spider-planar with respect to {{s₁, t₁}, {s₂, t₂}}, then the paths P₁ and P₂ as in Corollary 10.9 exist. Because P₁ and P₂ are disjoint, P₁ contains a path R₁, internally vertex-disjoint from the frame of Q, connecting a vertex a on the interior of s₂s₁t₂ to a vertex c on the interior of s₂t₁t₂. Because P₂ is vertex-disjoint from R₁, it contains a path P₂, internally vertex-disjoint from the frame of Q and R₁, connecting a vertex b on the interior of as₂c to a vertex d on the interior of at₂c. But now R₁ and R₂ contradict Lemma 10.4.

¨

Upon combining 10.10 with 10.1, 9.1, and 8.2, we obtain the following.

Lemma 10.11. Suppose that S is completely plated and there exists a C that contains no digons. Then |S| is embeddable on the cylinder.

¨

We now wish to show that this embedding of |S| determines a cylindrical embedding of S.

11. A Thin Red Line

We continue to retain the assumptions given at the beginning of section 3.6: S is 3-connected, loopless, and simply signed, and satisfies the barrier condition; and G(S) is non-binary but GF(4)-representable.

Theorem 11.1. If S is completely plated and has a frame, then S is simply red-line cylindrical.

Note: We will be considering the cases wherein S has no frame in the next section, which will complete our proof of Theorem 1.2.

Proof. We delete any tertiary bridges of S and embed the underlying graph |S¢| of the resulting graph S¢ on the cylinder such that its infinite faces are bordered by C₁ and C_n, thus determining an embedding of S¢. As in the proof of Lemma 6.2, there is a sequence of faces F₀, F₁, …, F_m for which F₀ and F_m are the infinite faces of the embedding and F_i and F_i+1 share an edge in their border. Furthermore, we may assume that this sequence of faces meets only one panel in each segment of the graph. We now draw a red line on S, starting in F₀, and progressing through F₁, F₂, … , F_n, each time passing through one edge a single time to move from one face to the next, never returning to a visited face. Let R be the collection of edges crossed by the red line. We may switch our frame so that the negative edges of the frame are exactly those frame-edges in R.

Let Q be a red panel of S. Q is balanced, so Q\R is balanced. Furthermore, Q\R has two components, Q₁ and Q₂. Since the frame edges of Q\R = Q₁ÈQ₂ are positive, we may switch Q\R in vertices interior to Q so that Q\R is all positive. We show that every edge of QÇR is negative.

Let e be one of the two frame-edges in QÇR; by previous comments e is negative. Let e¢ be another edge in QÇR. Then Q has a circle C containing e and e¢, which consists of e, e¢, and a pair of positive paths in Q₁ÈQ₂. C is positive because Q is balanced, so e¢ is negative.

Therefore our embedding of S¢ is simply red-line cylindrical. If C₁ had a tertiary bridge in S, then we embed this edge on the cylinder in the infinite face bordered by C₁, crossing the red line or not according to whether the edge is negative. We embed any tertiary bridge of C_n in the same manner to obtain a simple red-line embedding of S.

¨

As an immediate corollary we obtain:

Theorem 11.2. If a complete plating of S has a frame, then S is plate-cylindrical.

¨

12. Digons and the Completion of the Non-barrier Case

With the exception of section 3.10, the results to this point with respect to the non-barrier case have not disallowed digons, with the exception of not allowing C to contain digons.

We still retain the assumptions that S is 3-connected, loopless, and simply signed, S satisfies the barrier condition, and G(S) is non-binary and GF(4)-representable. We shall also assume that S is completely plated. Note that, by lemmas 8.1 and 9.2, if S has a frame, then S can have at most two digons, each formed by a tertiary bridge.

Lemma 12.1. If S has no frame, then C is of one of the following three forms:

i) A digon and a non-digon (the D-N case),

ii) A pair of digons (the D-D case), or

iii) A pair of digons and a non-digon (the D-N-D case).

Proof. We index C so that C_j is a barrier between C_i and C_k iff i < j < k or k < j < i. A repetition of arguments used in Lemmas 8.1 and 9.3 allows us to conclude that we may have at most two digons in S, one of which C₁ or contains an edge of C₁, the other of which is C_n or contains an edge of C_n.

We assume that C has as few digons as possible. If n = 2 the lemma is proved, so we may assume that n ³ 3. Suppose that C₁ is a digon but C₃ is not. Because S is 2-connected there are a pair of vertex-disjoint paths connecting C₁ to C₂, and thus S contains a negative circle C₁¢ that is vertex-disjoint from C₃, C₄, … , C_n and that contains edges of both C₁ and C₂. We remove C₁ and C₂ from C and replace it with C₁¢ to obtain a collection C¢, and then add to C¢ any more negative circles (none of which is a digon) it needs to be maximal. But C¢ has fewer digons than C, contradicting the assumption of minimality of the number of digons in C. Thus n = 3 and both C₁ and C₃ = C_n are digons.

¨

Tacit in the final paragraph of the previous proof is the following.

Corollary 12.2. If S has a pair of vertex-disjoint negative circles, neither of which is a digon, then S has a frame.

¨

The following result is perhaps the most technical yet.

Lemma 12.3. Suppose S has no frame. In any of the three cases given in Lemma 12.1, S is cylindrical.

Proof. We index C as usual, and assume C₁ is a digon. By repeating previous analysis, we see that the only other digon may be C_n or one formed by an edge of C_n and a tertiary bridge of C_n.

Case 1: D-N.

Let C₁ be a digon and C₂ = C_n be a non-digon. As before, we may assume that C₂ has at most two bridges, and if there are two such bridges one is a tertiary bridge e.

Let V(C₁) = {a, b}. Suppose there are two paths P₁ and P₂ internally vertex-disjoint from C₁ and C₂ with distinct respective endpoints v₁ and v₂ in C₂. Suppose there are similar paths P₃ and P₄ connecting b to vertices v₃ and v₄ on C₂. If P₃ÈP₄ meets P₁ÈP₂ then S has a frame. If v₁, v₃, v₂, v₄ are in clockwise order around C₂ then we obtain a bad drum or an evil minor as in Lemma 7.2. Thus C₂ contains edge-disjoint paths R_a and R_b such that all paths internally vertex-disjoint from C₁ÈC₂ connecting C₁ to C₂ connect a to vertices in R_a and b to vertices in R_b. Furthermore, V(C₂) = V(R_aÈR_b). Let P_a = {P : P is a path internally vertex-disjoint from C₁ÈC₂ connecting a to C₂}, and define P_b similarly. Let S_a = R_aÈ(ÈP_a) and let S_b = R_bÈ(ÈP_b). Note that the only edges in S not in C₁ÈS_aÈS_b are e and any edges in C₂\(R_aÈR_b).

Claim 1. If R_b\R_a is nonempty and e does not have an endpoint interior to R_a, then S_a is a positive triangle.

Proof of Claim 1. We switch S so that R_a is all-positive. If S_a is unbalanced, we obtain an evil minor using C₁, C₂, a negative circle in S_a and a path in S_b that is vertex-disjoint from S_a and is internally vertex-disjoint from C₁ÈC₂. Thus S_a is balanced. Since a and the endpoints of R_a separate S_a from b, S_a must have been plated out, and is a positive triangle. ¨

Proof of 12.2 continued. If e exists and has no endpoint in the interior of either R_a or R_b then both S_a and S_b are positive triangles, and S is clearly cylindrical. At least one of R_a\R_b and R_b\R_a is nonempty; we assume the latter. We may also assume that if e exists, it has both its endpoints in R_b. Thus we assume that S_a is a positive triangle. We switch C₂ so that its only negative edge is the lone edge in R_a. Note too that S can have no degree-3 vertices, so V(R_b) = V(C₂).

If two paths in P_b are of opposite sign, then S contains an evil minor (if the union of the two paths contains a negative circle) or a bad drum (otherwise). Thus we may switch S on vertices not in C₂Èa so that all edges in S_b are positive. If e does not exist, then S_b is also a negative triangle, and again S is cylindrical. Thus we assume that e exists.

Now, e and R_a are connected by two minimal paths R_b¢ and R_b² in C₂. If eÈa is a barrier between R_b¢ and R_b² in S_b, then R_b¢ and R_b² are each a single edge or a vertex, and P_b consists of edges with b as one endpoint and one of the three or four vertices of R_b as the other. In this case, S is cylindrical. Thus we assume that there is a path P in S_b, internally vertex-disjoint from R_b, connecting a vertex in R_b¢ to a vertex in R_b². Because P_b contains paths from b to the endpoints of R_a and P cannot be part of a secondary bridge, we may assume that the endpoints of P are the endpoints of R_a. Let a¢ and a² be the endpoints of R_a meeting R_b¢ and R_b² respectively.

There is a path bz which is internally vertex-disjoint from PÈR_b that connects b to a vertex z interior to P. If P is not a barrier between b and R_b in S_b, then there is without loss of generality a path P₁ in S_b that is internally vertex-disjoint from PÈR_b which connects b to a vertex in R_b¢\a¢. But now (S_aÈC₁ÈPÈP₁ÈR_bÈe)\a¢a² (where a¢a² is the lone edge in R_a) is a bad drum. Thus P is a barrier between b and R_b in S_b.

We assume that we have chosen P and bz so that the length of bz is minimal. Let U = È{P₀ : P₀ a path in S_b internally vertex-disjoint from bÈP connecting b to P}. If |V(UÇP)| > 1 then we contradict the minimality of bz. Thus U = z and bz is a single edge. We may now also assume that P has only one bridge.

Let C₃ be the non-digon negative circle in C₁Èaa¢zb and let C₄ be the non-digon negative circle in C₁Èaa²zb.

If there is a path P₂ in S_b that is internally vertex-disjoint from PÈR_b and connects a vertex in R_b¢\a¢ to a vertex in za²\z then S_b contains a non-digon negative circle which is vertex-disjoint from C₃, which by Lemma 12.2 gives a contradiction. Thus all paths that are internally vertex-disjoint from PÈR_b and connect R_b¢\a¢ to P meet P on a¢z. Let z¢ be the end-vertex among all such paths that is closest to z on a¢z. Similarly, all paths that are internally vertex-disjoint from PÈR_b and connect R_b²\a² to P meet P on a²z. We define z² similarly as well.

Because P has only one bridge, and by the last paragraph, {a