ARS MATHEMATICA CONTEMPORANEA ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 15 (2018) 383-406 https://doi.org/10.26493/1855-3974.1282.378 (Also available at http://amc-journal.eu) Characterizing all graphs with 2-exceptional edges* Drago Bokalf Faculty of Natural Sciences and Mathematics, University ofMaribor, Slovenia Jesús Leaños * Academic Unit of Mathematics, Autonomous University of Zacatecas, Mexico Received 11 January 2017, accepted 20 June 2018, published online 6 Aúgúst 2018 Dirac and Shuster in 1954 exhibited a simple proof of Kuratowski theorem by showing that any 1-crossing-critical edge of G belongs to a Kuratowski subdivision of G. In 1983, Siran extended this result to any 2-crossing-critical edge e with endvertices b and c of a graph G with crossing number at least two, whenever no two blocks of G - b - c contain all its vertices. Calling an edge f of G k-exceptional whenever f is k-crossing-critical and it does not belong to any Kuratowski subgraph of G, he showed that simple 3-connected graphs with k-exceptional edges exist for any k > 6, and they exist even for arbitrarily large difference of cr(G) - cr(G - f). In 1991, Kochol constructed such examples for any k > 4, and commented that Siran's result holds for any simple graph. Examining the case when two blocks contain all the vertices of G - b - c, we show that graphs with k-exceptional edges exist for any k > 2, albeit not necessarily simple. We confirm that no such simple graphs with 2-exceptional edges exist by applying the techniques of the recent characterization of 2-crossing-critical graphs to explicitly describe the set of all graphs with 2-exceptional edges and noting they all contain parallel edges. In this context, the paper can be read as an accessible prelude to the characterization of 2-crossing-critical graphs. Keywords: Kuratowski subgraphs, crossing number, exceptional edges. Math. Subj. Class.: 05C10, 05C62 * Both authors would like to acknowledge the Crossing Number Workshop 2016inStrobl, Austria, where parts of this research took place. We deeply acknowledge the significant effort of the referee 1 for improving the clarity of some technical details of the arguments in our paper. tD. Bokal was partially supported by the Slovenian Research Agency projects L7-5459 and J1—8130. * Research started while on sabbatical leave at Maribor University. Partially supported by CONACyT Grant 179867 and by the grant Internationalisation of Slovene higher education within the framework of the Operational Programme for Human Resources Development 2007-2013. E-mail addresses: drago.bokal@um.si (Drago Bokal), jleanos@matematicas.reduaz.mx (Jesus Leafios) ©® This work is licensed under https://creativecommons.org/licenses/by/3.0/ Abstract 384 Ars Math. Contemp. 15 (2018) 441-466 1 Introduction The crossing number cr(G) of a graph G is the minimum number of pairwise crossings of edges in a drawing of G in the plane. An edge e of a graph G is said to be k-crossing-critical, if cr(G) > k > cr(G - e), and a graph is k-crossing-critical, if each its edge is k-crossing-critical. Therefore K3,3 and K5 are the only 3-connected 1-crossing-critical graphs. Any subdivision of K3,3 or K5 in G is called a Kuratowski subgraph of G and an edge e is a Kuratowski edge, if e belongs to a Kuratowski subgraph of G. Any edge of G which is not a Kuratowski edge, will be called a non-Kuratowski edge. Following [12], we call an edge e of G k-exceptional if e is k-crossing-critical and e is a non-Kuratowski edge. Note that the existence of a k-exceptional edge in G for k > 0 implies the existence of a Kuratowski subgraph, and hence that G is non-planar. Since loops are irrelevant for crossing number purposes, all graphs in this paper are loopless, but they may have multiple edges. In their simple proof of Kuratowski theorem from 1954, Dirac and Shuster established that any 1-crossing-critical edge e of a graph G belongs to a Kuratowski subdivision of G [6]. In 1983, Siran showed that the number of non-Kuratowski edges (and hence the number of exceptional edges) of a 3-connected simple non-planar graph of order at least 6 is at most 4 [13]. The following statement was exhibited in the same year. Statement 1.1 (Theorem 2 in [12]). Let e be a crossing-critical edge of a graph G, for which cr(G — e) < 1. Then e belongs to a Kuratowski subgraph of G. Figure 1: A minimal graph with two 2-exceptional edges. We have found a family of exceptions (see Figure 1) to Statement 1.1, i.e. a family of graphs with 2-exceptional edges. That such graphs exist was already exhibited by Kochol [8], who noted without proof that Sirffl's result may only be true for simple graphs. Closely investigating Siran's proof, it establishes [12] the following: Theorem 1.2 (Theorem 2 in [12]). Let e with endvertices b and c be a crossing-critical edge of a graph G for which cr(G — e) < 1. If no two blocks of G — b — c contain all its vertices, then e belongs to a Kuratowski subgraph of G. The correct statement indicates that the structure of graphs with 2-exceptional edges is limited, and the aim of the present paper is to characterize these graphs, i.e. to explicitly describe the family E of graphs with 2-exceptional edges. The rest of this paper is organized as follows. In the following section, we exhibit some known and new properties of Kuratowski edges in graphs, and offer their characterization in Theorem 2.6, as well as introduce our main result. In Section 3, we sketch our D. Bokal and J. Leanos: Characterizing all graphs with 2-exceptional edges 385 overall approach, which follows a simplified version of the recent characterizatizaton of 2-crossing-critical graphs [4]. The description of all 3-connected graphs with 2-exceptional edges is given in Section 4, along with the proof of the sufficiency direction of the characterization and some other properties of graphs with 2-exceptional edges. The remainder of the paper is devoted to proving necessity of the characterization of 3-connected graphs with 2-exceptional edges. A skeleton graph, the basic subgraph that is used to describe 3-connected graphs with exceptional 2-edges, is studied in Section 5. Bridges of the skeleton graph are studied in Section 6. Also the necessity of characterization is established there. We conclude with some corollaries bearing upon existence of k-exceptional edges and some open problems in Section 7. 2 Kuratowski edges First we introduce some notation, aligned with the notation of [4]. Any vertex of a graph G of degree at least 3 is called a node of G. A branch is a maximal path with no internal nodes connecting two nodes of G. Two distinct nodes u, v of a subdivision K of K33 are said to be independent if any u, v-path in K contains a node of K different from u and v, i.e. if there is no branch between them. Let A, B be either two subsets of V(G) or two subgraphs of G. Then, an A, B-path is a path with first end in A and last end in B that is internally disjoint from both A and B. When A = {s} and B = {t} are just vertices, we shorten the notation to just s, t-path. When the ends need to be emphasized, we write P = sPt = [sPt], the former emphasizing ends of P and the latter emphasizing that the complete path with ends is considered. When either end or both ends of P are removed from the path, we use P - t = [sPt), P - s = (sPt], and P - s - t = (sPt). We refer to these paths as the (semi) open paths P. Let G be a graph and H its subgraph. A path P is H-avoiding, if all the non-end vertices and all the edges of P are not in H. The ends of an H-avoiding path are allowed to be in H. In [13], J. Siran gave a characterization of Kuratowski edges in k-connected graphs with k > 3, cf. Lemmas 2.1 and 2.2. In this section, we extend his a characterization to any graph. Next two lemmas were proved in [13] and will be very useful for our purposes. Lemma 2.1 (Lemma 1 in [13]). Let K be a subdivision of K3,3 and let u, v be distinct vertices of K. Let K' := K + P be a graph obtained by joining u, v with a path P internally disjoint of K. Then any edge of P is Kuratowski edge of K' if and only if u, v are not independent nodes of K. Lemma 2.2 (Lemma 2 in [13]). Let G be a 3-connected non-planar graph. Let e = uv be an edge of G which belongs to no subdivision of K33 in G. Then u, v are independent vertices of any subdivision of K3,3 in G. Although [13] considered only simple graphs, it is easy to see that the two lemmas apply to multigraphs as well. Our first statement is an easy exercise. Lemma 2.3. Let G be a graph and let G' be a subdivision of G. Let e be an edge of G and let P be the path of G' obtained by subdividing e. The following are equivalent: (i) e is a Kuratowski edge of G, (ii) every edge of P is a Kuratowski edge of G', 386 Ars Math. Contemp. 15 (2018) 441-466 (iii) some edge of P is a Kuratowski edge of G'. The proof of our next result is essentially the same as that of Lemma 1 in [13]. Lemma 2.4. (i) Let K be a subdivision of K5 and let u,v be distinct vertices of K. Let K' := K + P be a graph obtained by joining u, v with a path P internally disjoint of K. Then any edge of P is a Kuratowski edge of K'. (ii) Let G be a 2-connected graph that contains a subdivision of K5 as a subgraph. Then every edge of G is a Kuratowski edge. Proof. For (i), one can easily check using the symmetry of K5 that there are exactly six homeomorphism classes of graphs to which K' can belong. In all of them, it is easy to find the required subdivision of K5 or K33 in K': if both u, v are on the same branch of K, a slight rerouting establishes the claim. In other cases we find a suitable K3,3 subdivision including a degree-three vertex in one part, and its nearest degree at least 3 vertices in the other part. For (ii), let e be an edge of G with ends u and v and let K be a subgraph of G, which is isomorphic to a subdivision of K5. If e G K, we are done. Thus, we may assume that e is not an edge of K. By Menger's theorem, G contains two disjoint paths P1 := uP1x1 and P2 := vP2x2 with xi, x2 G V(K) such that V(K) n Pi = {xi} for i = 1,2. Now by applying (i) to P := x1 P1uevP2x2 and K, we have that e is a Kuratowski edge. □ The following is immediate from the definition of exceptional edge, Kuratowski's theorem and Lemma 2.4. Lemma 2.5. If G is a 2-connected graph containing exceptional edges, then G contains at least one Kuratowski subgraph and every Kuratowski subgraph of G is a subdivision of K33. The above gives the following characterization of Kuratowski edges in general graphs: Theorem 2.6. Let G be a graph and let e be an edge of G. Then e is a Kuratowski edge of G if and only if G contains a Kuratowski subgraph K and a path P such that: (i) P contains e, (ii) P joins distinct vertices u, v of K, (iii) u, v are not independent nodes of K, and (iv) either P is contained in K or P is internally disjoint from K. Proof. The necessity part is immediate: if e is a Kuratowski edge of G, then e belongs to a Kuratowski subgraph K1 and K := K1, P := e satisfy conditions (i)-(iv). The sufficiency follows from previous lemmas: assume that G contains subgraphs K and P satisfying (i)-(iv), and apply Lemma 2.1 or 2.4 to the pair K,P depending on whether K is a subdivision of K33 or K5. □ This characterization is important due to the following corollary, which allows us to restrict ourselves to 2-connected graphs when characterizing all graphs with 2-exceptional edges: D. Bokal and J. Leanos: Characterizing all graphs with 2-exceptional edges 387 Corollary 2.7. Let G be a graph, let e be an edge of G and let B be the block of G containing e. Then e is a Kuratowski edge of G if and only if e is a Kuratowski edge of B. Following [12], for a (possibly empty) subset S of vertices of G, a pair (H, K) of subgraphs of G is an S-decomposition, if (i) each edge of G belongs to precisely one of H, K and (ii) H n K = S. For |S| = 0,1, let H+ = H, K+ = K, and for |S| = 2, let H+ (respectively K+) be obtained from H (respectively, K) by adding an edge between the two vertices of S. Lemma 2.8. Let G be a graph with a 2-exceptional edge and let (H, K) be an S-decomposition of G with |S| < 2. Then, precisely one of H+, K + is non-planar. Proof. If both are planar, so is G, a contradiction, so at least one is non-planar. Suppose that both are non-planar. As e is not on any Kuratowski graph of G, G - e has the same Kuratowski graphs as G. Let KH be a Kuratowski graph of H + and Kk a Kuratowski graph of K +. Since at most one branch of Kk and KH contains S, for each K g {Kk , Kh }, every drawing of K has a crossed edge that is not an edge of the graph in {Kk , Kh } \ {K}. This shows that any drawing of Kk U Kh has at least two crossings, implying that cr(G - e) > 2, a contradiction. □ For k = 0,1,2,3, let £k be the family of k-connected graphs that contain 2-exceptional edges. Our main theorem describes these sets, but recursive description of £2 \ £3 requires an additional lemma: Lemma 2.9 ([12]). Let (H, K) be an {u, v}-decomposition of G andsuppose that cr(H) = cr(H +). Then, cr(G) = cr(K + Auv) + cr(H), where A is the maximum number of edge-disjoint paths from u to v in H. Theorem 2.10. Let G be a graph that has a 2-exceptional edge e with endvertices b and c. Then 1. G g £0 \ £ 1 is disconnected, all but one of its components are planar, and the non-planar component belongs to £1. 2. G g £1 \ £2 is connected, but not 2-connected, all but one of its blocks are planar, and the non-planar block belongs to £2. 3. G g £2 \ £3 is obtained from a subdivision of G' g £3 by replacing its edge st of multiplicity ^ with a planar graph H containing vertices s and t, such that H + st is 2-connected and there are at least ^ edge-disjoint s, t-paths in H. 4. G g £3 is a cyclization of four tiles, as described in Theorem 4.2. Proof. Claims 1 and 2 follow from applying Lemma 2.8, with |S| = 0,1, respectively. As we defer the proof of Theorem 4.2 to the next sections, we only need to prove Claim 3. Suppose that (H, K) is a {u, v}-decomposition of G that has exceptional edges. By Lemma 2.8, we may assume H+ is planar. Then by Lemma 2.9, cr(G) = cr(K + Auv) and cr(G — e) = cr((K — e) + Auv). Therefore, e is exceptional in K + Auv. Applying 388 Ars Math. Contemp. 15 (2018) 441-466 this reduction to any (H, K) decomposition in which H has vertices not in K reduces G to a subdivision of a graph in E3. This reduction has a constructive counterpart: any edge f of a graph in E2 can be subdivided, yielding a graph of E2. If the original edge was exceptional, so are both new edges. Furthermore, if e = uv is not the only exceptional edge of G, then e can be replaced by any planar 2-connected H, for which H + uv is also planar. The resulting graph is again in E2. Moreover, if uv has multiplicity A, some of its edges can be replaced by H simultaneously, provided H has at least that many edge-disjoint u, v-paths. Thus, any graph of E2 can be obtained starting with a graph in E3, applying subdivisions and replacing edges by described planar graphs, proving Claim 3. □ 3 Tile decomposition method For clarity, we describe the structure of our characterization of graphs with 2-exceptional edges in this section. It will follow the ideas of recent characterization of 2-crossing-critical graphs [4]. The approach can be abstracted into the following steps, which allow to decompose an abstract graph with properties of interest into smaller pieces called tiles. The tiles are a tool often applied in the investigation of crossing critical graphs [2, 3, 4, 7, 9, 10, 11]. The method structures arguments as follows: 1. Limit connectivity of graphs of interest. In both instances, we focus on 3-connected graphs, showing how to obtain graphs of lower connectivity from these and identifying exceptional less connected instances. For us, this step is simple as all graphs fit the pattern; in characterization of 2-crossing-critical graphs, it involved analyzing the exceptional graphs. 2. Identify a skeleton graph K. In the case of 2-crossing-critical graphs, the skeleton graph K is V10. In our case, it is the graph K in which contracting the edge incident with two degree three vertices produces K5. 3. Study drawings or embeddings of the skeleton graph. In the case of 2-crossing-critical graphs, V10 has two nonhomeomorphic drawings in the plane, which turned to be better analyzed as two essentially different projective-planar embeddings. For a graph G with 2-exceptional edge e and the skeleton graph K, we show that in any optimal drawing of G - e, the subdrawing of K - e is determined up to homeomor-phism. 4. Find a skeleton graph H = K and its drawing/embedding that offers sufficient structure for finding tiles. Usually this amounts to a skeleton graph, for which in the selected embedding, all bridges lie in well-controlled faces. For 2-crossing-critical graphs, there were three steps (friendly embedding, pre-tidy V10, tidy V10). Showing existence of such embeddings and skeleton graphs turned to be an important step in both cases. After this step, a standard quadruple was introduced in both cases to carry the information about the investigated graph G, its selected drawing or embedding n, and the tidy skeleton graph K = H C G that were required for subsequent proofs. Once a special skeleton graph and its drawing are defined, introduce a standard labelling with respect to that skeleton and its drawing. 5. Restrict bridges of (parts of) the skeleton graph. In the case of 2-crossing-critical graphs, bridges of V10 are shown to be either edges or small stars, and their attachments are near in the V10 subdivision. In our case, we show that there exists a D. Bokal and J. Leanos: Characterizing all graphs with 2-exceptional edges 389 skeleton graph K, such that all its bridges that are not edges lie in the infinite face of some of its optimal drawings, and that after removing the K4 subgraph of the skeleton with its parallel edges, we (roughly) obtain a join of two 3-connected planar graphs. 6. Combine bridges into tiles. In the case of 2-crossing-critical graphs, this analysis relies on identifying types of edges in the V10 subdivision and then splitting pieces between two consecutive edges of a specific type. Our instance is simpler: we show that our bridges constitute a sequence of four tiles, whose cyclization yields a graph of interest. 7. Prove that every tiled structure yields a graph of interest. Once the structure is determined, this is usually an easy task, and to confirm intuition about the listed steps, it can even be done as soon as the tiles are conjectured. We conclude this section by introducing the needed notation related to tiles. As in our approach we do not need the gadgets limiting crossing numbers of tiles, only the very basics are needed. For most recent developments on the theory of tiles, see [3, 4]. A tile is a triple T = (G, A, p), where G is a graph and A, p are two disjoint sequences of distinct vertices of G, called the left and right wall of T, respectively. Two tiles T = (G, A, p) and T' = (G',A',p') are compatible, if |p| = |A'|. The join of two compatible tiles T and T' with p = (p1,..., pw) and A' = (A1...,AW) is defined as the tile T ( T' := (G'', A, p'), where G'' is the graph obtained from the disjoint union of G and G' by identifying p4 with Aj, for i = 1,..., w. Specially, if p4 = Aj is a vertex with precisely two neighbors (after the identification), we replace it with a single edge in G'' of multiplicity equal to the smaller of the multiplicities of the edges incident with pi = Aj. This technical detail is important when considering 3-connected graphs. Since the operation ( is associative, we can safely define the join of a compatible sequence of tiles T = (T0, T1,..., Tm) as (T = T0 ( T1 ( ... ( Tm. The cyclization of a self-compatible tile T = (G, A, p), denoted by o T, is the ordinary graph obtained from G by identifying Aj with p4 for i = 1,..., w. The cyclization of a self-compatible sequence of tiles T = (T0, T\,..., Tm) is o T := o((T). Again, possible vertices with two neighbors are replaced with an edge maintaining smaller edge multiplicity, as above. We will also need the concept of a reversed tile of T, which is the tile with the two walls exchanged, T« = (G, p, A). 4 3-connected graphs with 2-exceptional edges In this section, we describe the class of graphs whose members are precisely all the 3-connected graphs containing at least one 2-exceptional edge. In particular, we define such a class and show that all its elements are 3-connected and have 2-exceptional edges. In the following sections, we show that any graph with 2-exceptional edges belongs to this class. For i > 1, let G1 = u^ be an edge of multiplicity i, and Oj = (G1, (uj), (vj)) a corresponding tile. Let O be the family of all tiles Oj, i > 1. For i,j > 1, let jG2 be the graph obtained by identifying the vertices vj and uj of Oj and Oj, respectively. Then lG\ has a vertex w of degree i + j and two vertices uj, vj of degree i, j, respectively, see Figure 2. By jQj = (jG^, (uj), (vj, w)), we denote the tile constructed using 390 Ars Math. Contemp. 15 (2018) 441-466 Let si, s2, «3 and s4 be the vertices of K4. We use H = °H° ^ to denote the graph obtained from such a K4 by doubling the edges of the path s4s1s2s3 and adding to s3 and s4 a new edge leading to a new vertex w2 and w1, respectively (see Figure 2). The graph Hi = °Hj 1 is obtained from the disjoint union of H and G1 by identifying si of H with vi of G1, and letjHi = jHi,1 be the graph obtained from the disjoint union of Gj and Hi by identifying the vertex uj of G1 with s2 of Hi. Note that for i, j =0 the graph iHj is defined independently of G1, G"[, which only exist for i, j > 1. For k a positive integer, we denote by j Hlk the graph obtained from j Hi by increasing multiplicity of one of the edges s1s3 or s2s4 (but not both) to k. Finally, for l a positive integer, the graph j Hlk t is obtained from j Hlk by increasing the multiplicity of the edge S3S4 to l. For any integers i, j, k and l such that i, j > 0, and k, l > 1, we define a tile jRk ; = (jHk [, (ui, w2), (vj, w1)); for i, j = 0, we set u° = s1 and v° = s2, respectively. We use R to denote the family consisting of all the tiles j R®k t and all the tiles that can be obtained from these by arbitrarily increasing multiplicity of each edge on the path s4s1s2s3 (which must, however, remain at least two). Let P be the family that contains each tile T that can be obtained from any 3-connected planar G containing a degree three vertex x with neighbors u, v, w as T = (G - x, (u), (v, w)). In addition to these, let us assume that P also contain each tile iQj, with i, j > 1. A pre-exceptional sequence T of tiles has four tiles (T, T2, T3, T4), such that: (C1) T1 = Oil e O, (C2) T2 e P, (C3) T3 = i3 Rjk3,13 eR, (C4) TT e P, and (C5) if T2 = i2 Qj2, then i3 > 1 (respectively, if T4T = i4 Qj4 then j3 > 1). Then there are exactly six types of pre-exceptional sequences: depending on whether T2 (respectively, T4) comes from a 3-connected planar graph, or T2 = i2 Qj2 (respectively, if T4t = i4Qj4), we have sixteen types of T's, which are reduced to six by considering (C5) and the symmetry. Such six types of T's are shown in Figure 3. The signature of a pre-exceptional sequence T = (I\, T2, T3, T4) is an ordered list of integers 2. The following technical observation is also needed in our proof. Lemma 4.1. Let G be a graph, and let {u, v, w} be a vertex cut of G such that {u, v, w} is not the neighborhood of a vertex in G. Let Gi be a non-trivial bridge of {u, v, w} in G, and obtain Gi by connecting a new vertex ti to each of u, v, w. Then, G is 3-connected, if and only if each of Gi is 3-connected. Proof. First we assume that G is 3-connected. Letp, q be any two vertices in Gi. If p = ti, choose as p any vertex of Gj for j = i. The three internally disjoint paths in G connecting p and q can be easily converted to three internally disjoint paths connecting ti and q. If both p and q are distinct from ti, there are three internally disjoint paths pP1q, pP2q, pP3q in G. At least two of these paths are in Gi, and if the third one is not, it uses two of the vertices u, v, w. We may assume it is pPuuP3vPv q. But then, pPuutivPv q is a path of Gi, internally disjoint from P1, P2, completing the necessity direction. For sufficiency direction, let p, q be two arbitrary vertices of G. If they are in the same Gi, there are three internally disjoint paths in Gi that connect them, which can easily be augmented to paths in G. If p e Gi, q e Gj, i = j, then let pPUputi, pPpvti, pPw wti be three internally disjoint paths between p and ti in Gi, and similarly qPuutj, qPqvtj, qPqwtj be three internally disjointpaths between q and tj in Gj. Then, pPpuPuq, pPpvPqq, pPp wPq q are three internally disjoint paths between p and q in G. □ Theorem 4.2. (I) A graph G is in E3, if and only if G can be described as a cyclization of an exceptional sequence T = (T1,T2,T3, T4). 392 Ars Math. Contemp. 15 (2018) 441-466 (II) G has two 2-exceptional edges if and only if k3 = 1 in T3 = 13 Rj l3. (III) If G € E0, then cr(G) = 2. Proof. We show Claims (II) and (III), and sufficiency of Claim (I). The necessity of Claim (I) is covered in the subsequent sections. Let G be a cyclization of T = (Ti, T2, T3, T4) as above. In this proof, we use the notation and drawings provided in Figure 3. Without loss of generality, we may assume that the edge of T3 with endvertices si and s3 has multiplicity k3. In order to show that G € E3, we need verify that it is 3-connected and that it contains 2-exceptional edges. From the construction of G and Lemma 4.1 it is not difficult to see that G is 3-connected. Thus it is enough to show that the edge e = s2s4 is a 2-exceptional edge of G. In other words, we need to show that: (11) cr(G - e) < 1, (12) e is not a Kuratowski edge of G, and (13) cr(G) > 2. For r € {2,4}, we assume that in any drawing of G under consideration, the restriction of such a drawing to Tr is a plane graph. Indeed, since there exists a drawing of Tr that has all the wall vertices on the same face, such a face can be made the infinite face by inversion and the resulting drawing or its mirror can be used to form the required drawing of G. Then, regardless the multiplicities of the edges in or T3, the drawings in Figure 3 imply that cr(G) < 2 and cr(G - e) < 1, which reduces (I1) to (I3). For (I2), seeking a contradiction, assume that e lies on some Kuratowski subgraph K of G. As G has exactly 4 vertices not in T2 U T4 (namely, si, s2, s3 and s4), then for some r € {2,4}, Tr contains at least one node of K. On the other hand, the planarity of Tr and the fact that Tr contains only three wall vertices imply that at least one node of K is not in Tr. Because Tr is joined to exactly three vertices of G - Tr, K is not homeomorphic to K5. Then K is homeomorphic to K3 3. Since any set of four edges with an end in Tr and the other in G - Tr contain at least one pair of parallel edges, the number of nodes of K in Tr must be exactly one. In particular, this implies that si, s2, s3, and s4 are nodes of K, and that each of T2 and T4 contains exactly one node of K. Since the node of K in T4 is joined to s2 and s4, these vertices belong to the same chromatic class in K, however, as e = s2s4 is an edge in K, s2 and s4 belong to distinct chromatic classes, a contradiction. Now we show that (I3) cr(G) > 2. We analyze separately two cases, depending on whether min p(T) =2 or min p(T) = 1. Case 1. min p(T) > 2. Let H be the graph that results by deleting from G all the vertices of T2 and T4 that are not in the face containing the wall vertices. Note that if T2 (respectively, T4) comes from a 3-connected planar graph, then T2 n H (respectively, T4 n H) is a cycle of length at least 3, and in the other case, T2 n H = T2 = i2 Qj2 (respectively, T4 n H = T4 = i4Qj4). Clearly, cr(G) > cr(H). Now we verify that cr(G) > 2 by showing that cr(H) > 2. Let D be an optimal drawing of H. As usual, we assume that parallel edges are placed very closely to each other in D, and hence, that they have the same number of crossings. Then if any edge of the path P := s4sis2s3 is crossed in D, we are done. D. Bokal and J. Leanos: Characterizing all graphs with 2-exceptional edges 393 Let h be an edge of H with endvertices s1 and S3. From Figure 3, we can see that H contains a subgraph J homeomorphic to K3 3 that avoids e and h (the thick edges). Indeed, the nodes of J are s1, s2, s3, s4 and p, q the endvertices of T1. If the restriction D[J] of D to J has at least two crossings, or at least one of e, h is crossed in D, we are done. Thus we assume that cr(D[J]) = 1 and that both e, h are clean in D. In particular, note that the restriction D' of D to the subgraph H' of H induced by s1, s2, s3 and s4 is a plane graph and that H' contains to K4 as subgraph. On the other hand, min p(T) > 2 implies that the number of parallel edges between p and q is at least 2, and hence both p and q are in the same face of D', or we are done. By using stereographic projection if necessary, we may assume that such a face is the infinite face of D'. Then exactly one vertex of H', say s', is in the triangular finite face formed by the other three vertices. Moreover, from the definition of J it follows that at least one of p or q is joined with s' by a path P', which is internally disjoint of H'. Since, for r = 1, 2, H contains at least two p, sr-paths edge disjoint and internally disjoint from H', then s' € {s1, s2}, or such p, sr-paths provide the required crossings. If s' € {s3, s4}, then P' crosses at least one edge of E(P) U {e, h}, which is impossible. Case 2. min p(T) = 1 and 13 > 2. Since T2 and T4 are connected and 13 > 2, then G contains a subgraph H which is homeomorphic to the graph shown in Figure 4. As before, we verify cr(G) > 2 by showing that cr(H) > 2. Let C be the double cycle of H whose vertices are s1, s2, s3, and s4, and let D be an optimal drawing of H. If any edge of C is crossed, we are done. Then we may assume that the restriction D[C] of D looks like in Figure 4. Then u and v must be in the same face of D[C]: otherwise, at least one edge of C is crossed by the edge with endvertices u and v and we are done. Without loss of generality, we assume that both are in the infinite face of D[C], as shown in Figure 4. Note that the paths s1us3 and s2vs4 cross each other because they have alternating ends in C. Similarly, if the edges s1s3 and s2s4 are in the same face of C, we have the required crossing. Then at least one of them is in the infinite face of C and such an edge must cross with some of s1us3 or s2vs4 providing the required crossing. This proves (I3) and hence sufficiency of (I). The inequality in (I3) was independently checked with the crossing number computing tool of Chimani et al. [5] SI s2 Figure 4: A drawing of H. Now we show (II) that G has two 2-exceptional edges if and only if k3 = 1 in T3 = 3 Rfca h. Note that, by symmetry, the argument used in (I2) also shows that any edge of G with endvetices s1 and s3 is a not a Kuratowski edge. Let us denote by K3 the set of edges of G with ends s1 and s3. On the other hand, from the definition ofi3 i3, we know that e is the only edge of G with ends s2 and s4. Then Lemmas 2.2 and 2.5 imply that s1 and s3 (respectively, s2 and v u 394 Ars Math. Contemp. 15 (2018) 441-466 s4) are in the same chromatic class of nodes of a subdivision K of K3,3 in G. We derive a contradiction from the assumption that G contains a non-Kuratowski edge e' G K3 U {e}. Then Lemma 2.2 implies that e' joins two nodes in the same chromatic class of nodes of K. Furthermore, since e' G K3 U {e}, then it must have an end in {si, s2, «3, s4} and the other in a node of K \ {si, s2, «3, s4}. The existence of such an e' implies that K U K3 U {e, e'} C G contains K5 as subdivision. This and Lemma 2.5 imply that all the edges of G are Kuratowski edges, a contradiction. Let us assume that k3 = 1 in T3 = i3 R^,3,1 . Then K3 consists of an edge h. From (I1) and (I3) we have cr(G) = 2. Now, if we draw e inside of the square s1s2s3s4 in Figure 3, we get, in all the cases, an optimal drawing of G in which h is crossed by e. This proves that h is 2-crossing-critical, and hence e and h are both 2-exceptional edges. On the other hand, since cr(G) = 2 for any k3 > 1, then if k3 > 2 we have that no edge in K3 is 2-crossing-critical and since K3 U {e} are the only non-Kuratowski edges of G, then k3 > 1 implies that e is the only 2-exceptional edge of G. This proves (II). Finally, we show (III) that if G G Eo, then cr(G) = 2. (1) If G g E3 we are done by (I1) and (I3). (2) If G G E2 \ E3 then, by Theorem 2.10(3), there exists G' G E3 such that cr(G) = cr(G'). Since cr(G') = 2, we are done. (3) If G G E1 \E2 then, by Theorem 2.10(2), all but one of blocks of G, say B, are planar and B g E2. Then cr(G) = cr(B). If B G E3 (respectively B G E2 \ E3) we are done by (1) (respectively (2)). (4) If G G E0 \ E1 then, by Theorem 2.10(1), all but one of the components of G, say C, are planar and C g E1. Then cr(G) = cr(C). Clearly, exactly one of the following is true: C g E3, C g E2 \ E3, or C g E1 \ E2. Note that these three cases have been studied, respectively, in (1), (2), and (3), and in all of them the conclusion is cr(C) = 2, as required. □ 5 The skeleton graph In this section, we present the skeleton graph, which is the essential structure of 3-connected graphs with 2-exceptional edges. First, we introduce some notation, aligned with the notation of [4]. Let H be a subdivision of a graph G and let e be an edge of G. If s and t are the ends of e, then we denote by sHt the s, t-path of H which results from subdividing e. We use vst to denote an arbitrary, but fixed, vertex of (sHt). Following this general notation, we turn our attention to the specific graph K'', which we show to constitute the skeleton of graphs in E3. It is depicted in Figure 5. We always use the labelling from the figure (and we call it standard labelling), so {{a, b, c}, {x, y, z}} constitute the bipartition of a subdivision K = K3 3, and bc, yz are the exceptional edges of K''. We will use K' for K + bc, and refer to it as apre-skeleton. A bypass of a non-Kuratowski edge e of K'' is the union of any two K3 3 branches that together with e form a cycle containing exactly 3 nodes of K''. A bypass is open, if the endvertices of e are removed from it and closed if they are contained in it. The common node t G {a, b, c, x, y, z} of the K'' branches used in the bypass is the peak of the bypass, and we denote the bypass by Kt. For instance, Kx = bK''xK''c and Kb = yK''bK''z. D. Bokal and J. Leanos: Characterizing all graphs with 2-exceptional edges 395 a b c Figure 5: The skeleton graph K''. We will be vague by using Kt both for open and closed bypass, but where distinction will be required, (Kt) is open and [Kt] is closed. Besides bypasses, claws at a and x will play a significant role. We define them by Da := aK'x U aK'y U aK'z and Dx := xK'a U xK'b U xK'c. A talon of a claw is its one degree vertex. A claw is open, if we remove its talons. Again, we will use [Da] and [Dx] for closed, and (Da), (Dx) for open claws. The graph K4' := K'' \ ((Da) U (Dx)) is a subdivision of K4. When H = K'' is a subdivision of K'', we extend the definition of bypasses and claws naturally to H. The next lemmas restrict the possible bridges of a skeleton graph in G. The first one shows that graphs in E3 do not contain a subdivision of a graph, obtained from K' by adding a path with ends in two distinct bypasses, except for three exceptions. Lemma 5.1. Let H := K' + P, where P is a path joining two distinct elements of {(Kx), (Ky), (Kz)} and internally disjoint from K'. Then every edge of H is a Kura-towski edge, or P joins distinct vertices of {x, y, z}. Proof. By Lemma 2.3, we may assume that H has no vertices of degree 2. In particular, P is an edge. Assume that P does not join distinct vertices of {x, y, z}. Let q and r be the endvertices of P. As (Kx), (Ky), and (Kz) are open, P does not join two vertices of {a, b, c}. By Lemma 2.1, we have that all the edges in H except bc are Kuratowski edges. It remains to show that in each case, bc belongs to a subdivision of K3 3. By the symmetry of K', we need only analyze the cases in which q G {y, vyb} and r G {vbz, vcz}. If q = y and r = vbz, then H \ {by, cx} is the required subdivision. If q = y and r = vcz, then H \ {bx, cy} is the required subdivision. If q = vyb and r = vbz, then H \ {cx, bvbz} is the required subdivision. If q = vyb and r = vcz, then H \ {x} is the required subdivision. □ The next lemma restricts paths adjacent to paths linking two nodes of K. Lemma 5.2. Let H := K' + P + Q, where P is a path joining two distinct elements of {x, y, z} and internally disjoint from K', and Q is a path joining an inner vertex p of P with a vertex q G V (K') \ V ((Da)) and internally disjoint from K' + P. Then every edge of H is a Kuratowski edge, or cr(H — bc) > 2, or q G P. Proof. Without loss of generality, we may assume P = yPz. By Lemma 2.3, we may assume that H has no vertices of degree 2. Lemma 2.1 implies that all the edges in H except bc and possibly edges of P U Q are Kuratowski edges. 396 Ars Math. Contemp. 15 (2018) 441-466 Since q G V((Da)) and H has no vertices of degree 2, then q is a node of H distinct from a. If q G {y, z}, we are done. If q = x, then (K' — bc) U P U Q is a subdivision of K3 4, and cr(H) > 2. So we assume that q G {b, c}. By symmetry, we may assume that q = b. In this case, H \ {cx, by, bz} is a subdivision of K3,3 that uses the edge bc and all edges of P U Q, concluding the proof. □ Lemma 5.1 implies the following useful structure of optimal drawings of G — e: Lemma 5.3. Let G G E3 and let e be its 2-exceptional edge with endvertices b and c, and let K3,3 = K C G. If D is an optimal drawing of G — e and DK is the induced subdrawing of K, then the ends of e lie on a face of DK that is not incident with its crossing. Proof. By Lemma 2.2, b, c are independent nodes of K, so they are on the boundary of some (possibly different) face(s) of DK. Up to homeomorphism, DK is drawn in Figure 6. The parts in the bipartition of K3,3 are {1,3,5} and {2,4,6}. Any pair of independent nodes of K lies on a common face of DK, and E1, E2 are the only faces contradicting the conclusion of Lemma 5.3. 2 1 Figure 6: The unique drawing of K3 3, up to homeomorphisms. By symmetry, we may assume b, c lie in E1, implying {b, c} = {2, 6}. As cr(G — e) < 1, the crossing of DK is the only crossing of D. As cr(G) > 2, there is an arc in D connecting the two segments of the boundary of E1 having b, c as ends. As this path avoids the only crossing of D, it is a path in G — e that connects two distinct open bc-bypasses, and at least one of its endvertices is not a node of K, contradicting Lemma 5.1. Therefore, b, c lie either in O1 or O2, and neither of these is incident with the crossing of D, as claimed. □ In the analysis, we use the following result from [12]. We also repeat some notation. Lemma 5.4 (Lemma 3 in [12]). Let G be a 3-connected non-planar graph, and let e be a non-Kuratowski edge of G with endvertices b and c. Then the graph G/e is 2-connected but not 3-connected, and the graph G — b — c is connected, but not 2-connected. Let H := G — b — c and let T(H) be the block-cutpoint tree of the graph H. Lemma 5.4 implies that T(H) is a non-trivial tree. According to Theorem 1.2, G — b — c has all vertices in two blocks for any graph G with 2-exceptional edge bc. By now, we are ready to establish that the pre-skeleton graph is a subdivision contained in any graph with a 2-exceptional edge. D. Bokal and J. Leanos: Characterizing all graphs with 2-exceptional edges 397 Theorem 5.5. Let G gE3 with e its 2-exceptional edge with endvertices b and c. There exist a pre-skeleton subgraph H with K' = H C G and an edge f of G, such that H + f is a subdivision of the skeleton graph K''. Proof. By Lemma 2.5, G has a subdivision K = K3,3. As e is not a Kuratowski edge, e is not in K. Let uPv be any maximal K-avoiding path containing e. As G is 3-connected, Theorem 2.6 implies that u, v are distinct nodes of K; we choose the standard labelling of K such that {u, v} = {b, c}. As G is 3-connected, P is either an edge, or there exists a K + P-avoiding path pQq connecting a vertex of p G (P) with a vertex q G G \ V (P). One of the paths bPQq and cPQq contains e, hence Theorem 2.6 applied to it implies q = a. Then, K U P U Q is a subdivision of K34 containing e, a contradiction to e not being a Kuratowski edge. Hence Q does not exist and bPc is just a single edge, showing that H := K + e is a pre-skeleton in G. Next we prove that there exists a K'-avoiding path Q, connecting two nodes from {x, y, z}. We may be forced to change K' for this. Claim 5.6. There exists a pre-skeleton subdivision K' in G, such that K' n K' contains the closed bypasses of e (in particular, b, c, x, y, z are nodes of K'), and there is an K'-avoiding path P of G connecting q, r G {x, y, z}. Proof. As there are two blocks of H = G - b - c containing all its vertices, at least two vertices p, q of {x, y, z} are in the same block B of H. We may assume without loss of generality that they are y and z. As B is 2-connected, there are two internally disjoint paths yPiz and yP2z in B. By Lemma 5.1, the intersection of Pi U P2 with Kx U Ky U Kz is contained in {x, y, z}. Suppose that x G P1 U P2 .If either P1 n (Da) or P2 n (Da) is empty, it is the required path and K' = K'. So we may assume they are both non-empty. Let a' be a vertex of P1 U P2, such that xDaa' has no vertex of P1 U P2. We may assume a' G P^ As (P1 U a'Dax) n K' is contained in [Da], if' := (K' - (Da)) U (P1 U a'DaaDax) is the required skeleton and P2 is the required K'-avoiding y, z-path. Now we may assume x G P1 U P2. Then x, y, z split C := P1 U P2 into three arcs Cxy := xCy, Cyz := yCz, and Czx := zCx, such that C = xCyyCzzCx. Let ax, ay, az be the a-closest vertices of P1 U P2 in xDaa, yDaa, zDaa, respectively; they may all be equal to a. If each segment of Cxy, Cyz, Czx contains a vertex of ax, ay, az, then let a'' be the one of ax, ay, az in Cyz and let a' be any other one. Then, C U (([axDaa] U [ayDaa] U [azDaa]) - (aDaa'') - (Cyz)) contains an x, y, z-claw T with center a' and is internally disjoint from Cyz. Hence, K' = (K' - (Da)) U T is the required pre-skeleton and Cyz the y, z-path internally disjoint from K'. If a segment Cxy, Cyz, Czx contains two vertices of ax, ay, az, and a segment C0 contains none, we relabel {x, y, z}, so that Cyz = C0. Then Da U P1 U P2 - (Cyz) contains a claw T with center a and talons x, y, z so that Cyz is internally disjoint from it; again, K' = (K' - (Da)) U T is the required pre-skeleton and Cyz the y, z-path internally disjoint from K'. If a segment C3 of Cxy, Cyz, Czx contains all three vertices of ax, ay, az, then in C U Da, there is a C-avoiding path pRq from (C3) to C - [C3]. We relabel {x, y, z}, so that p G Cxy and q G Cxz. Then, (C UpRq) - (Cyz) contains an x, y, z-claw T, with center in p, so that Cyz is internally disjoint from it; again, = (K' - (Da)) U T is the required pre-skeleton and Cyz the y, z-path internally disjoint from K'. □ 398 Ars Math. Contemp. 15 (2018) 441-466 Without loss of generality, we label the nodes of K so that P = yPz. Claim 5.7. The path yPz from Claim 5.6 is an edge. Proof. Seeking a contradiction, assume that P has an internal vertex v. Consider an optimal drawing D of G - e. Since K c G - e and cr(G - e) < 1, we have cr(G - e) = 1. Thus the drawing D restricted to K is homeomorphic to the drawing DK in Figure 6. Because G is 3-connected, G - y - z contains a path Q from v to K - y - z, which is internally disjoint from K U P .If q is the endvertex of Q in K, Lemma 5.2 implies q G V (Da). Since the crossing d of DK is the only crossing of D, no edge of P U Q is crossed in D. Hence P is drawn in a face of DK incident with two independent nodes. By the symmetry of Dk, we may assume that v G E or v G Oi. See Figure 6. If v G Oi, then {y, z} = {4, 6} or {y, z} = {1,5}. By the symmetry of DK, we may assume {y, z} = {4,6}, and hence x = 2. This implies that a =1 or a = 5. If a = 5, then {b, c} = {1,3}. Since cr(G - e) < cr(G), then there must be a simple arc a of D contained in O2, with endpoints on its boundary and separating b from c (1 from 3 in Figure 6). Since d is the only crossing of D, a corresponds to a path R of G which joins two vertices of V(K') \ V(Da). Lemma 5.1 implies R joins x and z. Now it is easy to see that K' U P U R contains a subdivision of K5, contradicting Lemma 2.4. For the final case, v G Ei. Then, without loss of generality, P connects y = 2 and z = 6, implying x = 4. As q is on some path in the boundary of Ei, a can be any of the vertices 1, 3, or 5. Suppose a =1. This implies bc = 35, contradicting Lemma 5.3. Suppose next a = 3, implying bc = 15. As cr(G) > 2, there is an arc in D separating 1 from 5 in Oi. By Lemma 5.1 and as there is only one crossing in D, this arc is a path R from 4 to 6. As K' U P U R has a subdivision of K5, it contradicts Lemma 2.4. The subcase a = 5 is similar, with bc = 13 and 2R4. □ Thus f is an edge connecting y and z, and K'Uf is a subdivision of K'', as claimed. □ Proposition 5.8. Let G G £3 and let K'' = H C G be its skeleton subgraph with standard labelling. Then G does not contain a path P internally disjoint from K'' with endvertices in any of the pairs {a, b}, {a, c}, {x, y}, {x, z}. Proof. Let u, v be the endvertices of P. If {u, v} G {{a, b}, {a, c}, {x, y}, {x, z}} then the subgraph (K'' + P) c G contains K5 as subdivision. This and Lemma 2.4 imply that G has no exceptional edges, a contradiction. □ Corollary 5.9. Let G G £3. Any non-Kuratowski edge g of G is parallel to e or f. Proof. Let u, v be the endvertices of g. By Lemma 2.2, we know that u, v are independent vertices of K and by Proposition 5.8, we have that {u, v} = {b, c} or {u, v} = {y, z}. □ Let e and f be the exceptional edges of G g£3. The graph obtained from G by adding a parallel edge f' to f is also an exception to Statement 1.1, but such a graph contains only e as an exceptional edge, because both edges f and f' are non-critical. These observations yield the following corollary to Theorem 4.2: Corollary 5.10. Let G G £3. The number of 2-exceptional edges of G is at most two. D. Bokal and J. Leanos: Characterizing all graphs with 2-exceptional edges 399 Proof. By Corollary 5.9, it is enough to show that if f and f' are parallel edges of G, then they are not critical. Suppose an arbitrary of them is and let it be f. Then cr(G - f) < 1. As K C G - f, there exists an optimal drawing D of G - f in which f' G K has no crossings. By drawing f very close to f' in D, we get a drawing of G with exactly one crossing, a contradiction implying that f is not critical and hence not exceptional. □ 6 Bridges of the skeleton graph Let H be a subgraph of a graph G. An H-bridge is either an edge not in H together with its two incident vertices that are in H or is obtained from a component J of G - V(H) by adding all edges incident with a vertex of J together with their incident vertices in H. This concept will be helpful for the remainder of this section. A bridge is trivial, if it is just an edge, and non-trivial otherwise. For a graph H and its bridge B, any vertex of att(B) := V(H) n V(B) is an attachment of B. First we exhibit the structure of an optimal drawing of G - e. Lemma 6.1. Let G G E3, let K'' be its skeleton graph, let e be its 2-exceptional edge with endvertices b and c, and let f be a non-Kuratowski edge not parallel to e. If D is an optimal drawing of G - e, then the drawing D restricted to K + f is homeomorphic to the drawing in Figure 7 (right) and b, c are the ends of e. Proof. Let D be an optimal drawing of G - e and K the K3 3 subdivision in K''. As e is a 2-exceptional edge, D has a unique crossing and D restricted to K is homeomorphic to the drawing DK in Figure 7 (left). Using symmetry, stereographic projection, and Lemma 5.3, we may assume that the ends of e are b and c. Hence, f G {xy, yz, xz}. If f G {xy, xz}, cr(G) > 2 implies there is a path P of G - e that is by Lemma 5.1 drawn from y to z in E, yielding a K5 subdivision in K'' U P, contradicting Lemma 2.4. Thus y and z are the ends of f and the drawing D restricted to K + f is homeomorphic to the drawing in Figure 7 (right), as required. □ b b x x Figure 7: If D is an optimal drawing of G - e, then the drawing D restricted to K + f is homeomorphic to the right drawing. In what follows, we call (G, H, e, D) a standard quadruple, abbreviated sq, if G G E3, K" = H C G, such that H has standard labelling, e is a 2-exceptional edge of G, and D is an optimal drawing of G - e, with the induced subdrawing of H - e drawn as in Figure 7. Lemma 6.2. Let G G E3. Then, there exists a standard quadruple (G, H, e, D) containing G. 400 Ars Math. Contemp. 15 (2018) 441-466 Proof. As G g £3, there exists a 2-exceptional edge e of G. Theorem 5.5 guarantees existence of the skeleton graph H in G, that is a subdivision of K''. Finally, Lemma 6.1 yields existence of the desired drawing D of G — e. □ Lemma 6.3. Let G g £3, let K'' = H C G with the standard labelling. If B is a bridge of H, v g att(B), and v is not a node of H, then att(B) C [Da] U [Dx]. Proof. Let v be as in the statement. Seeking a contradiction, suppose that there exists u g att(B) \ ([D0] U [Dx]). Then u g (Ky) U (Kz) (or equivalently, u g (K6) U (Kc)). Since B is connected, it contains an u, v-path, say P. From Lemma 5.1 and the hypothesis that v is not a node of H, we have that v g (aHx). By the symmetry of K4', we need only analyze the case in which u = vby. But in such a case, (H U P) \ {ay, bx, cz} is a subdivision of K3 3 containing both bc and yz as edges, which contradicts that bc is a 2-exceptional edge. □ Let G g £3. In what follows, we will denote with H4 as the subgraph of G induced by the four vertices that are ends of the non-Kuratowski edges of G. By Corollary 5.9, H4 is well-defined for any G, i.e. it is independent of the choice of H. Lemma 6.4. Let (G, H, e, D) be a standard quadruple of a graph G g £3. The subgraph H4 of G is isomorphic to K4 with some multiple edges, and it has only one bridge that contains both a and x and the only crossing of D. Proof. As G is 3-connected and H4 is induced in G, H4 has no trivial bridges. As there exists an H4-avoiding path aHx, a and x are in the same H4-bridge B, and that bridge is crossed in D. If B is the only bridge, we are done, otherwise let B' be any other bridge. As G is 3-connected, each of B, B' has at least three attachments. As e G B' and the only crossing of D is in B, B' is drawn planarly in D. Then D implies the attachments of B' are either b, y, z or c, y, z, both contradicting Lemma 5.2. Let {u, v} G {{c, z}, {b, z}, {b, y}, {c, y}}. Now consider the branch of H connecting u to v. If such branch is not an edge, then it has one internal vertex, say w. Using the 3-connectivity, the drawing D, and the fact that B is the only bridge in H4, we know that there is a path, that is internally disjoint from H, connecting w to a vertex in (Da) U (Dx). However, no such path exists by Lemma 6.3. □ For a graph G G £3, we will denote the only bridge of its graph H4 by B4. Lemma 6.5. Let K'' = H C G and let P be a path from u G (Ka) to v G [Kx] with {u, v} = {a, x}, and internally disjoint from H. Then every edge of H + P is a Kuratowski edge. The claim also holds with the role of a and x exchanged. Proof. By Lemma 2.3, we may assume that H has no vertices of degree 2. It is enough to show that in each case H has a subdivision of K3 3 or K5 containing either bc or yz. By the symmetry of H, we need only analyze the following cases; the same arguments also show the claim with the role of a and x interchanged: If u = vaz and v = vcx, (H U P) \ {by, cz, xHv} is a subdivision of K3,3. If u = vaz and v = c, (H U P) \ {xc, cz, by} is a subdivision of K3,3. If u = a and v = vcx, (H U P) \ {xv} is a subdivision of K5. If u = a and v = c, (H U P) — xc is a subdivision of K5. □ D. Bokal and J. Leanos: Characterizing all graphs with 2-exceptional edges 401 Lemma 6.6. Let (G, H, e, D) be a standard quadruple of a graph G G E3. If P is a b, y-path of length at least 2 contained in B4, then P intersects [aHxj. Proof. Seeking a contradiction suppose that P n [aHxj = 0. By Lemma 6.5 and our hypothesis, at least one of P n (Ka) or P n (Kx) is empty. By symmetry, we may assume that P n (Ka) = 0. If P n (Kx) is also empty, then P is internally disjoint from H. Then, (H — (by)) U P is a different choice of H for G whose structure contradicts Lemma 6.4, as the H4 produced by this H has a subdivided edge by. Hence, P n (Kx) is nonempty. Lemma 6.1 and disjointness of P from (Da) + x imply that there is a H-bridge B with attachments in y and (xHbj. By the previous paragraph, at least one attachment is in (xHb). However, any path in B from y to (xHb) contradicts Lemma 6.5, concluding the proof. □ Lemma 6.7. Let (G, H, e, D) be a standard quadruple of a graph G G E3. Then, there exist vertices vc and vz in B4, such that vcc and vzz are the only attaching edges of B4 at c and z. Moreover, these edges are crossed in D. Proof. We show the claim for vcc, the claim for vzz is analogous. Let x be the crossing of D. By Lemma 6.5, there is no H-avoiding path in B4 from (xHc) to [Da] avoiding x. Let F be any face of D incident with the segment (x Hc). As V(dF) C V([Da]) U V((xHc)), existence of a vertex in (xHc) would contradict 3-connectivity of G. Hence, (xHc) lies on some edge cvc of B4, and cvc is crossed in D. Analogously, we can conclude that (x Hz) lies on some edge vzz of B4, and hence cvc and vzz are the only two crossing edges of D. By Lemma 6.5 we know that G does not have a path internally disjoint from H, with an end in c and the other end belonging to (Ka). Thus, the existence of any other edge of B4 attaching at c, together with the location of c in D imply that at least one of vz z or zy is crossed by some edge in B4 — cvc, contradicting that cr(D) = 1. □ Lemma 6.8. Let (G, H, e, D) be a standard quadruple of a graph G G E3. There exists K" ^ h' C G and an optimal drawing D' of G — e, such that a'z and ex' are edges of H', and any face incident with the crossing of D' has no bridges of H' drawn in it. Proof. By Lemma 6.7, there exist vertices vc and vz, such that cvc and zvz are edges of G. Moreover, cvc crosses zvz in D and such a crossing x is the only crossing of D. Let D'' be the subdrawing of D, induced by G — c — z. Since x is the only crossing of D, then b, vc, vz and y lie in the same face F of D''. Note that F contains (in the interior) vertices c and z. By Lemma 6.1, the boundary walk dF can be decomposed into bPivcP2vz P3yb. Note that if some P G {P1, P2, P3 } is not a path, then P must have a cut vertex, say w. By Lemma 6.7 we know that vc, y and vz, b are the only vertices of B4 adjacent to c and z, respectively. From this and the supposition that w is a cut vertex of P it follows that w is a cut vertex of G — e, which contradicts the connectivity of G — e. Thus we can assume that P1, P2 and P3 are paths. Define H' = H — (Da) — (Dx) U [bP1vcP2vzP3y] U cvc U zvz. We relabel a' := vz and x' := vc. Observing how H' is drawn in D, the claim follows with D = D'. □ A standard quadruple (G, H', e, D') from Lemma 6.8 is called a tidy standard quadruple, abbreviated tsq. 402 Ars Math. Contemp. 15 (2018) 441-466 Lemma 6.9. Let (G, H, e, D) be a tsq of a graph G G E3. Then, B = B4 — c — z has two cut vertices u, v in [aHi], and uHv is an edge of G, and any u, v-path in G avoiding H is an edge. Proof. Let F be the face of the subdrawing of D of the cycle C = bHxHaHyb not containing the crossing of D. As C is clean in D, dF = C. Tidiness implies that D[B] is contained in F and that D [B + by] is planar. Now, let F' be the face of the subdrawing D[B] containing the edge by. Note that D[B] is a drawing of B4 — c — z and hence contains no edges of H4. We decompose the boundary of F' into two paths, bHxHaHy and P as follows: As H is tidy, bHxHaHy is on the boundary of F', and let P be the remaining part of the boundary, i.e. dF' = yPbHxHaHy. As P is a b, y-path in B, P intersects [aHx] in a vertex v by Lemma 6.6. As v appears twice in the boundary of F', it is a cut-vertex of B. Let P = yP1vP2b and assume that P1 — v, P2 — v do not intersect [aHx]. Then, H4 + P1 + P2 + vHxc + vHaz is a subdivision of K5, a contradiction to Lemma 2.4. Thus there is a vertex u G P n [aHx], u = v, and u is another cut-vertex of B. Now consider any {u, v}-bridge B' in B with attachments in both u and v that has a vertex w distinct from u, v. As G is 3-connected, either B' contains (i) b or (ii) y, or (iii) an attachment of B on H + cx + az. The latter option (iii) is dismissed by tidiness: az, cx are the only edges from c, z to B in a tsq, and the vertices b, y can be interpreted as (i) or (ii). The former two options (i) and (ii) both contradict the claim that both u, v are cut vertices of B. As any H-avoiding u, v-path is either an edge uv or contained in a B-bridge with attachments u, v, the lemma follows. □ Lemma 6.10. Let (G, H, e, D) be a tsq. If there are no two internally disjoint b, x- (respectively a, y-) paths in B4, then there is a cut vertex v G bHx (respectively, v' G aHy), such that bv (yv') is an edge and any H-bridge B' C B4 attaching at b (y) is an edge bv (yv'). Proof. We prove the claim for bHx, the proof for aHy is analogous. Suppose there are no two disjoint b, x-paths, implying there is a cut-vertex v G bHx. Let u be any vertex of bHv. As G is 3-connected, there is a path from u to G — (bHv) in G — b — v. This path is in B, and by Lemma 5.1, it does not attach to H4. Therefore it attaches in (Da) U (Dx) — bHv, a contradiction to v being a cut. Therefore if there is a cut vertex v, then bv is an edge. The same argument implies that any H-bridge B' C B attaching at b has attachments only at b and v, and is therefore a trivial bridge. □ Lemma 6.11. Let (G, H, e, D) be a tsq. The edges by, bz, cy have multiplicity at least two. Proof. Suppose on the contrary that at least one of the mentioned edges has multiplicity one. First we handle bz and cy with a slightly modified drawing with the existing crossing of xc, az replaced by a crossing of an edge with assumed multiplicity one, and for by we also twist the modified drawing: Augment the sub-drawing D[B4] by contracting the edges xc, az slightly with c, z following their edge's drawings past the crossing, so that xc, az no longer cross, and call this new drawing D' (cf. Figure 8 left). As B4 contains all the vertices of G and all edges not in B4 are connecting nodes of H4, it is a routine exercise to extend the drawing D' to a D. Bokal and J. Leanos: Characterizing all graphs with 2-exceptional edges 403 drawing of G with just one crossing, in which either bz is crossing cx or cy is crossing az, contradicting criticality of bc whenever either bz or cy have multiplicity one. Figure 8: A twist in a drawing demonstrating multiplicity of certain edges. For by, we need to twist D': As u is a cut-vertex of the bridge B by Lemma 6.9, the outer face of D' has the following boundary: bHxcxHuvHazaHyP\vuP2b. Let D'' be obtained by twisting D' at u, so that D'' is a drawing of B with the outer face bHxcxHuPlyHazaHuP2b (cf. Figure 8, right). Then D" can be augmented to a drawing of G in which the only crossing is between by and az, a contradiction. □ Lemma 6.12. Let (G, H, e, D) be a tsq. If there do not exist two edge disjoint p, q-paths in B4 for any of {p, q} G {{a, x}, {a, y}, {b, x}}, then cz has multiplicity at least two. Proof. In the proof, we use the drawings D' and D" defined in the proof of Lemma 6.11. For {p, q} = {b, x}, suppose there are no two edge disjoint b, x-paths. Therefore, there are no internally disjoint b, x-paths. By Lemma 6.10, there is a cut-vertex v in bHx and bv is an edge, and any other H-bridge attaching at b is a trivial edge bv. If the edge bv has multiplicity two, then there are two edge-disjoint b, x paths in B4: vP2uHx and vHx (they are edge disjoint, as them sharing an edge would imply G is not 3-connected). Hence the edge b, v has multiplicity one. If cz is a single edge, then the drawing D'' can be modified to a drawing of G in which the only crossing is of cz with bv, a contradiction establishing cz is a double edge. Symmetric arguments apply to the case {p, q} = {y, a}. In the final case of {p, q} = {a, x}, Lemma 6.9 implies there is an edge uv in G, such that u, v are cut-vertices, uv is a single edge and D" is obtained from D[B] by twisting at the vertex u. If cz is a single edge, D" can be augmented to a drawing of G by cz crossing uv as its only crossing, the final contradiction establishing the claim. □ Now we have all the ingredients to establish necessity in Theorem 4.2. Proof of necessity in Theorem 4.2, (i). Let G G E3, and let (G, H, e, D) be its tidy standard quadruple, whose existence is guaranteed by Lemma 6.8. By Lemma 6.9, there exist two vertices p, q in [aHx], such that G contains an edge h with endvertices p and q and any H-avoiding p, q-path is an edge. Let O be the union of all these edges; then T\ := (O, (p), (q)) G O. Without loss of generality, we may assume that aHx = aHqhpHx. By definition of the tidy standard quadruple, az and cx are edges of G. Furthermore, Lemma 6.10 asserts that either there is an edge g with endvertices b and v such that any b 404 Ars Math. Contemp. 15 (2018) 441-466 H-bridge B' C B4 attaching at b is an edge parallel to g, or there are two internally disjoint b, x-paths (in this case, we let b = v) in the bridge B4. Symmetrically by the same lemma, there is an edge g' with endvertices u, y with H-bridges within B4 restricted to edges parallel to g', or there are two internally-disjoint a, y-paths in B4 (in this case, we let y = u). Let H4 be the subgraph of G, induced by the vertices {b, c, y, z}. We let R to be obtained from H4 by adding the two edges az and cx, and, if b = v, all the edges which are parallel to g, and, if y = u, all the parallel edges to g'. Note that when T2 (respectively, T4) is a Q-tile, we have v = x (respectively u = a) in G due to suppression of vertices with two neighbors when joining tiles, but in R, we always have u = a and v = x. Lemma 6.11 implies that the edges by, bz, and cy have multiplicity at least 2. As bc is a single edge, we have that T3 = (R, (a, u), (x, v)) is a tile in R. Now consider the vertices p, v, and x. As cx is an edge, v is a vertex-cut in B4, which disconnects b from x, and x, v are two attachments of an R-bridge B'. As p is a vertex-cut in B4 disconnecting a from x, then {p, x, v} form a cut in G, or they are all equal. If they are a cut, then they are all three distinct as G is 3-connected. We first analyze the case when they are all distinct. Let P be a bridge of {p, x, v} disjoint from R, and let P' be the graph obtained from P by adding a vertex t adjacent to precisely its three attachments. As G is 3-connected, Lemma 4.1 implies that P' is 3-connected, so the tile T2 = (P, (p), (x, v)) is a tile in P. Suppose now that p = x = v. Then v = b. Let i be the multiplicity of the edge pq, and let j be the multiplicity of the edge vb. We set T2 = (®Qj, (q), (p, b)), which is a tile in P. Symmetric arguments applied to y, a, q, and u imply that there is a tile T4, such that T4" g P. As vertices with just two neighbors are suppressed when joining tiles, we have that G is a join oT of a pre-exceptional sequence T = (T, T2, T3, T4). To see that T is exceptional, assume that min p(T) = 1. Thus, after joining the tiles, one of the edges pq, bv, or yu is a single edge. This implies that in G, there are no two internally disjoint w, s-paths for one of {w, s} g {{a, x}, {a, y}, {b, x}}, and Lemma 6.12 implies cz has multiplicity at least two. In terms of 2 as desired. □ 7 Conclusions We conclude with some comments regarding the existence of k-exceptional edges. Theorem 4.2 immediately gives the following corollary, claimed by Siran [12] and Kochol [8]: Corollary 7.1. Let G be a simple graph and e its crossing-critical edge with cr(G — e) < 1. Then, e is a Kuratowski edge of G. It is also easy to obtain the following: Corollary 7.2. For any integer k > 2, there exist infinitely many 3-connected graphs with k-exceptional edges. Proof. For k = 2, the claim follows from Theorem 4.2. For higher k, we only sketch the proof by induction; an attentative reader will be able to provide the technical details. Let be the family of 3-connected graphs with k-exceptional edges containing a tidy skeleton subdivision H, such that G — az — bc — cz is planar. By induction and Theorem 4.2, we assume that Fk_1 is infinite for k > 3. Let G g be arbitrary. Assuming the standard labelling of H, we produce a graph G' g as follows: D. Bokal and J. Leanos: Characterizing all graphs with 2-exceptional edges 405 i) For G1, we make any edge of G - az - bc - cx have multiplicity at least k. Note that Gi is still planar. ii) For G2, we add to G1 single edges az, cx; this graph has crossing number 1 and any optimal drawing of G2 has az crossing cx. iii) For G3, we add the edge bc with multiplicity k - 1. In any optimal drawing, bc edges cross the edge az, implying the crossing number of the graph G to be at most k. Should any other edge be crossed, that would add at least k crossings, implying crossing number > k. As the edges of G need to cross at least twice (this is the technical detail we omit, but it is true due to the construction of graphs in F2), cr(G3) = k and cr(G3 - e) < k for any edge parallel to bc, hence G' = G3 has k-exceptional edges and the claim follows. □ Note that the graphs of Corollary 7.2 cannot be made simple by subdividing edges and connecting the new vertices in a cycle (the operation is called n-subdivision in [1]), as was done in [8]: then the new vertices introduced in n-paths would violate Lemma 2.5 and a K5 would be introduced in the new graph. Hence, the following remain open: Problem 7.3 ([8]). What is the smallest k, for which simple 3-connected graphs with k-exceptional edges exist? Clearly, 3 < k < 4. Hence, the simple graphs obtained by Kochol do not follow our tile structure, but as all the K3 3's of G need to share the endvertices of the exceptional edges, there may still exist an explicit description of graphs with k-exceptional edges. We therefore conclude with the following: Problem 7.4. Is there a descriptive characterization (i.e. a tile description) of 3-connected graphs with k-exceptional edges? References [1] D. Bokal, On the crossing numbers of Cartesian products with paths, J. Comb. Theory Ser. B 97 (2007), 381-384, doi:10.1016/j.jctb.2006.06.003. [2] D. Bokal, Infinite families of crossing-critical graphs with prescribed average degree and crossing number, J. Graph Theory 65 (2010), 139-162, doi:10.1002/jgt.20470. [3] D. Bokal, M. Bracic, M. Dernar and P. Hlineny, On degree properties of crossing-critical families of graphs, in: E. Di Giacomo and A. Lubiw (eds.), Graph Drawing and Network Visualization, Springer, Cham, volume 9411 of Lecture Notes in Computer Science, pp. 75-86, 2015, doi:10.1007/978-3-319-27261-0_7, revised selected papers from the 23rd International Symposium (GD 2015) held in Los Angeles, CA, September 24 - 26, 2015. [4] D. Bokal, B. Oporowski, R. B. Richter and G. Salazar, Characterizing 2-crossing-critical graphs, Adv. Appl. Math. 74 (2016), 23-208, doi:10.1016/j.aam.2015.10.003. [5] M. Chimani and T. Wiedera, An ILP-based proof system for the crossing number problem, in: P. Sankowski and C. Zaroliagis (eds.), 24th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum fur Informatik, Wadern, volume 57 of Leibniz International Proceedings in Informatics, pp. 29:1-29:13, 2016, papers from the symposium (ESA 2016) held in Aarhus, August 22 - 24, 2016. [6] G. A. Dirac and S. Schuster, A theorem of Kuratowski, Indag. Math. (Proceedings) 57 (1954), 343-348, doi:10.1016/s1385-7258(54)50043-0. 406 Ars Math. Contemp. 15 (2018) 441-466 [7] M. Kochol, Construction of crossing-critical graphs, Discrete Math. 66 (1987), 311-313, doi: 10.1016/0012-365x(87)90108-7. [8] M. Kochol, Linear jump of crossing number for non-Kuratowski edge of a graph, Rad. Mat. 7 (1991), 177-184. [9] B. Pinontoan and R. B. Richter, Crossing numbers of sequences of graphs II: Planar tiles, J. Graph Theory 42 (2003), 332-341, doi:10.1002/jgt.10097. [10] B. Pinontoan and R. B. Richter, Crossing numbers of sequences of graphs I: General tiles, Aus-tralas. J. Combin. 30 (2004), 197-206, https://ajc.maths.uq.edu.au/pdf/30/ ajc_v30_p197.pdf. [11] R. B. Richter and C. Thomassen, Minimal graphs with crossing number at least k, J. Comb. Theory Ser. B 58 (1993), 217-224, doi:10.1006/jctb.1993.1038. [12] J. Siran, Crossing-critical edges and Kuratowski subgraphs of a graph, J. Comb. Theory Ser. B 35 (1983), 83-92, doi:10.1016/0095-8956(83)90064-3. [13] J. Siran, Edges and Kuratowski subgraphs of nonplanar graphs, Math. Nachr. 113 (1983), 187190, doi:10.1002/mana.19831130118.