ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 17 (2019) 637-652
https://doi.org/10.26493/1855-3974.1474.d54
(Also available at http://amc-journal.eu)
Extremal embedded graphs
*
QiYan, Xian'anJin t
School of Mathematical Sciences, Xiamen University, Xiamen 361005, P. R. China
Received 3 September 2017, accepted 19 October 2019, published online 13 December 2019
Let G be a ribbon graph and ^(G) be the number of components of the virtual link formed from G as a cellularly embedded graph via the medial construction. In this paper we first prove that ^(G) < f (G)+ y (G), where f (G) and 7 (G) are the number of boundary components and Euler genus of G, respectively. A ribbon graph is said to be extremal if m(G) = f (G) + 7(G). We then obtain that a ribbon graph is extremal if and only if its Petrial is plane. We introduce a notion of extremal minor and provide an excluded extremal minor characterization for extremal ribbon graphs. We also point out that a related result in the monograph by Ellis-Monaghan and Moffatt is not correct and prove that two related conjectures raised by Huggett and Tawfik hold for more general ribbon graphs.
Keywords: Ribbon graph, medial graph, Petrie dual, extremal minor, orientation. Math. Subj. Class.: 05C10, 05C83, 57M15
1 Introduction
A cellularly embedded graph is a graph G embedded in a surface E such that every connected component of E - G is a 2-cell, called a face. If G c E, the homeomorphism class of the surface E generates an equivalence class of cellularly embedded graphs, and we say that cellularly embedded graphs are equal if they are in the same equivalence class. We assume familiarity with cellularly embedded graphs, referring the reader to [6, 13] for further details.
We use standard notations V(G), E(G) and F(G) to denote the sets of vertices, edges, and faces, respectively, of a cellularly embedded graph G and v(G) = |V(G)|, e(G) =
*We thank the anonymous referee for valuable comments and corrections. This work is supported by NSFC (Grant Number 11671336) and the Fundamental Research Funds for the Central Universities (No. 20720190062). t Corresponding author.
E-mail addresses: qiyanmath@163.com (Qi Yan), xajin@xmu.edu.cn (Xian'an Jin) ©® This work is licensed under https://creativecommons.org/licenses/by/4.0/
Abstract
638
ArsMath. Contemp. 17(2019)591-615
|E(G)| and f (G) = |F(G)|, respectively. In general, a finite number of connected cel-lularly embedded graphs will form a disconnected cellulary embedded graph. Let k(G) denote the number of connected components of G. A graph is said to be bipartite if it does not contain odd cycles. A face of a cellularly embedded graph is called even if its boundary has an even number of edges (it is possible that a single edge appears twice in the boundary of a face and under such circumstances the edge will be counted twice).
Let ^(G) be the number of components of the virtual link formed from a cellulary embedded graph G via the medial construction. It was originally called left-right paths of cellularly embedded graphs in [16]. Let TG(x, y) be the Tutte polynomial [17] of the graph G. It is shown in [10, 11] that
Tg(-1,-1) = ( —l)e(G)(-2)m(g)-1,
if G is embedded in the plane, the real projective plane or the torus. For many families of planar graphs, their link component numbers have been determined, see, for example, [5, 8, 14, 15].
Cellularly embedded graphs are equivalent to ribbon graphs. In this paper we mainly work in the language of ribbon graphs. In this paper we first prove that ^(G) < f (G) + Y(G) for any ribbon graph G, where f (G) and y(G) are the number of boundary components (i.e. faces of the corresponding cellularly embedded graph) and Euler genus of G, respectively. A ribbon graph is said to be extremal if ^(G) = f (G) + y(G) and a ribbon graph is plane if its Euler genus is zero. In [9], the authors studied extremal plane graphs and in [7], Huggett and Tawfik studied extremal cellularly embedded graphs on orientable surfaces of positive genus. In this paper we extend their results to any ribbon graph and also obtain that a ribbon graph is extremal if and only if its Petrial is plane. In [12], Moffatt introduced the notion of minors of ribbon graphs and gave an excluded minor characterization of the family of ribbon graphs that represent knot and link diagrams. In [3], Chudnovsky et al introduced a notion of bipartite minor and proved a bipartite analog of Wagner's theorem. In this paper we imitate them and introduce a notion of extremal minor and provide an excluded extremal minor characterization for extremal ribbon graphs.
In [7], Huggett and Tawfik also conjectured
Conjecture 1.1 ([7]). If G is an extremal graph cellularly embedded on a torus then each face of G is even.
Furthermore,
Conjecture 1.2 ([7]). If G is an extremal graph cellularly embedded on a torus then G is bipartite.
It is obvious Conjecture 1.2 implies Conjecture 1.1. In this paper, we shall show Conjecture 1.1 holds for any extremal cellularly embedded graphs and Conjecture 1.2 holds for any orientable extremal cellularly embeded graphs, but is not true for non-orientable extremal embedded graphs. We also point out that the second claim of Proposition 3.27 in [4] is not correct.
2 Preliminaries
There are several ways to represent cellularly embedded graphs, and it is often more convenient and natural to work in the language of one or the other of these representations.
Q. Yan and X. Jin: Extremal embedded graphs
639
Thus, we briefly describe ribbon graphs. We refer the readers to [1, 2] and the monograph [4] for details. Readers familiar with them can skip this section.
Definition 2.1 ([1]). A ribbon graph G = (V(G),E(G)) is a (possibly non-orientable) surface with boundary, represented as the union of two sets of topological discs, a set V(G) of vertices, and a set E(G) of edges such that
1.	the vertices and edges intersect in disjoint line segments, we call them common line segments;
2.	each such line segment lies on the boundary of precisely one vertex and precisely one edge;
3.	every edge contains exactly two such line segments.
If we delete the two common line segments from the boundary of an edge in a ribbon graph then we obtain exactly two disjoint line segments, we call them edge line segments of the edge. Two ribbon graphs are said to be equivalent or equal if there is a homeomor-phism between them that preserves the vertex-edge structure. A ribbon graph is said to be orientable if it is orientable when viewed as a surface with boundary. Similarly, the genus, g(G), of a ribbon graph G is its genus when viewed as a punctured surface. The genus of a disconnected ribbon graph is the sum of the genera of its connected components. The genus of a surface is not additive under connected sums. For example the connected sum of a torus and a real projective plane, which, are both surfaces of genus 1, is homeomor-phic to the connected sum of three real projective planes, a surface of genus 3. To get over this technical difficulty, the Euler genus, 7, which is additive under the connected sum, is defined. Let G be a connected ribbon graph. Then
12g(G), if G is orientable, |g(G), if G is non-orientable.
If G is not connected, then 7(G) is defined as the sum of the Euler genus of each of its connected components. We say that a ribbon graph G is a plane graph if 7(G) =0.
It is well known that ribbon graphs and cellularly embedded graphs are equivalent: if G is a cellularly embedded graph, a ribbon graph representation results from taking a small neighbourhood of the embedded graph G. Neighbourhoods of vertices of the graph G form the vertices of a ribbon graph, and neighbourhoods of the edges of the embedded graph form the edges of the ribbon graph. On the other hand, if G is a ribbon graph, we simply cap off the punctures to obtain a closed surface and then the core of the ribbon graph is exactly cellularly embedded in this surface. An example is given in Figure 1 [4]. Since cellularly embedded graphs and ribbon graphs are equivalent, we can, and will, move freely between these representations, choosing whichever is most convenient at the time for our purposes. In the context of ribbon graphs, f (G) is the number of boundary components of the ribbon graph G.
The Euler characteristic, x(G), of a ribbon graph G, is defined by
X(G) = v(G) - e(G) + f (G). It is related to the Euler genus by the following formula:
x(G) = v(G) - e(G) + f (G) = 2k(G) - 7(G).
640
Ars Math. Contemp. 17 (2019) 637-652
i
(a) A cellularly embedded graph G. (b) G as a ribbon graph.
Figure 1: Two presentations of the same embedded graph.
A loop (respectively, cycle) in a cellularly embedded graph is said to be non-orientable if its small neighbourhood is homeomorphic to a Mobius band. Otherwise it is said to be orientable. It is more obvious if we use the language of ribbon graphs.
We use the language of ribbon graphs to define the deletion and contraction of an edge. Let G = (V(G), E(G)) be a ribbon graph and e e E(G). We denote by G - e the ribbon graph obtained from G by deleting the edge e. We denote by G/e the ribbon graph obtained from G by contracting the edge e. In the case that e = (u, v) is not a loop, G/e is obtained from G by deleting e, u and v and adding a vertex disc along the boundary of e, u and v and in the case that e = (v, v) is a loop, G/e is obtained from G by deleting e and v and adding a vertex disc or two vertex discs along the boundary of e and v (it is an annulus if the loop is orientable and a Mobius band otherwise). Alternatively, G/e := (G* — e)*, where * represents the geometrical dual.
3 Medial graphs and Petrials
Medial graphs as a tool will be used very often throughout this paper. If G is cellularly embedded in E, we construct its medial graph Gm in the embedded surface by placing a vertex on each of its edges, and for each face f with boundary ei, e2,..., edf), drawing d(f) edges {e1, e2},..., {edff), e1} inside the face f along the boundary of f. It is obvious that Gm is also cellularly embedded in E. We can form the medial graph of a ribbon graph inside the ribbon graph as shown in Figure 2. In particular, the medial graph of an isolated vertex is a free loop. Another example is given in Figure 3. In the language of medial graphs, ^(G) is exactly the number of "straight-ahead" walks in the medial graph Gm, as described in [18].
Figure 2: The formation of the medial graph of a ribbon graph.
An all-crossing direction of Gm is an assignment of a direction to each edge of Gm in such a way that at each vertex v of Gm, when we follow the cyclic order of the directed
Q. Yan and X. Jin: Extremal embedded graphs
641
Figure 3: A non-orientable loop G and its medial graph Gm (^(G) = 2, red component and blue component).
edges incident to v, we find head, head, tail and tail. If Gm is equipped with an all-crossing direction, then we can partition the vertices of Gm into c-vertices and d-vertices according to the scheme shown in Figure 4. Accordingly edges of G are divided into c-edges and d-edges.
The Petrial of a cellularly embedded graph G, which we denote by Gx, is formed with the same vertices and edges as G, but for the faces taking the Petrie polygons, which are the result of closed "straight-ahead" walks in Gm (see Wilson [18]). Since the "straight-ahead" pattern effectively means crossing over each edge, when the graph is viewed as a ribbon graph, this is simply giving each edge a half-twist, and hence Gx is simply the result of giving a half-twist to all of the edges as shown in Figure 5. An example of a ribbon graph and its Petrial is given in Figure 7.
(a) c-vertex
(b) d-vertex
Figure 4: c-vertex and d-vertex.
Figure 5: Add a half-twist to an edge of a ribbon graph.
Lemma 3.1. Let G be a ribbon graph. Then
m(G) = f (Gx).
Proof. This follows immediately from Figure 6.
□
Notice that rather than adding a half-twist to each of the edges of G, we may add half-twists to only some of the edges of G. The result is a partial Petrial of G. Let G be a
642
Ars Math. Contemp. 17 (2019) 493-514
G
e
c
Gx
Figure 6: The relation between medial graph and Petrial.
ribbon graph and A C E(G). Then the partial Petrial, GT(A), of G with respect to A is the ribbon graph obtained from G by adding a half-twist to each of the edges in A. Let Orb(T) (G) = {GT(A) | A C E(G)} denote the set of all partial Petrials of G. Ellis-Monaghan and Moffatt in [4] claimed:
Proposition 3.2 ([4]). Let G be a ribbon graph. Then
1.	| Orb(T) (G)| is bounded above by two raised to the power of the number of cycles in G.
2.	if G is bipartite, then Gx = G.
In fact the second claim of Proposition 3.2 is not true. A counterexample is given below.
Example 3.3. As shown in Figure 7, we have 7(G2) = 0 and 7(GX) = 2, and hence G2 = GX but G is bipartite, contradicting the second claim of Proposition 3.2.
Figure 7: Counterexample G2 (and its Petrial GX) of the second claim of Proposition 3.2.
4 Upper bound and extremal graphs
In this section, we give some basic properties of ^(G), extending results in [7] and [9] from orientable ribbon graphs to non-orientable ones, and obtaining several new results at the same time.
Lemma 4.1. Let G + e be the ribbon graph obtained from a ribbon graph G by adding a new edge e connecting two (not necessarily distinct) vertices of G. Then
Proof. If e is a loop and the common line segments of the loop are adjacent, then there are two cases:
Case 1.1: If e is an orientable loop, then ^(G + e) = ^(G), as in Figure 8.
m(G) - 1 < m(G + e) < m(G) + 1.
Q. Yan and X. Jin: Extremal embedded graphs
643
Case 1.2: If e is a non-orientable loop, then + e) = ß(G) + 1, as in Figure 9.
Otherwise, there are also two cases (see Figure 10).
Figure 10: Case 2.1 and 2.2.
Case 2.1: If the arcs a (joining a and b) and ft (joining c and d) are contained in different components of G (here "components of G" means components of the virtual link formed from G via the medial construction, in the following we take this convention and it causes no confusion in the context), then ^(G + e) = ^(G) — 1.
Case 2.2: If the arcs a and ft are contained in same component of G, then there are two subcases.
Case 2.2.1: Along this component, if the order of the four endpoints of the two arcs a and
ft is a, b, c, d, then ^(G + e) = ^(G).
Case 2.2.2: If the order of the four endpoints of the two arcs a and ß is a, b,d,c, then MG + e) = MG) + 1.	□
644
Ars Math. Contemp. 17 (2019) 493-514
Theorem 4.2. Let G be a ribbon graph. Then
k(G) < MG) < f (G) + y(G).
Proof. It is trivial that k (G) < ^(G). Take a maximal forest F of G, it is obvious that ^(F) = k(G). There are e(G) - v(G) + k(G) edges of G outside F. By Lemma 4.1, we have
MG) < k(G) + (e(G) - v(G) + k(G)) = f (G) + y(G).	□
A ribbon graph G is called extremal if ^(G) = f (G) + y(G). The following lemma expresses ^(G) in terms of G and its petrial Gx.
Lemma 4.3. Let G be a ribbon graph. Then
MG)= y(G) + f (G) - y(Gx).
Proof. Note that
X(G) = v(G) - e(G) + f (G) = 2k(G) - y(G), X(GX) = v(Gx) - e(Gx) + f (Gx) = 2k(Gx) - y(Gx).
In addition, v(G) = v(Gx),e(G) = e(Gx), k(G) = k(Gx) and f (Gx) = ^(G) by Lemma 3.1. Hence ^(G) = y(G) + f (G) - y(Gx).	□
The upper bound in Theorem 4.2 is also a direct consequence of Lemma 4.3 since Y(Gx ) > 0. The following theorem is simple, but critical in the next two sections.
Theorem 4.4. A ribbon graph G is extremal if and only if y (Gx ) = 0, i.e. Gx is plane.
If G, P and Q are ribbon graphs, then we say that G is the join of P and Q, written G = P v Q, if G can be obtained by identifying an arc on the boundary of a vertex of P with an arc on the boundary of a vertex of Q as indicated in Figure 11. The two arcs that are identified do not intersect any common line segments.
(a) P	(b) Q	(c) P v Q
Figure 11: The join P v Q of P and Q.
Lemma 4.5. Let G = B1 v B2 v B3 v • • • v Bk. Then
k
MG) = ^ MB*) - k + 1. i=1

Q
Q
Q. Yan and X. Jin: Extremal embedded graphs
645
Proof. It suffices to show that Lemma 4.5 holds for k = 2. Let v be the new vertex of G formed by merging a vertex of Bi and a vertex of B2. Since v is a cut vertex, the arcs c\ and c2 must belong to a single component, and ci and c'2 must belong to different components, that is, splitting B1 V B2 at v into B1 and B2 increases the number of components by one, as in Figure 12. Thus ^(G) = ^(Bi) + ^(B2) - 1.	□
c2
(a) Bi V B2
(b) Bi
(c) B2
Figure 12: A component of Bi V B2 is split into a component of Bi and a component of B2.
Lemma 4.6. Let G be a ribbon graph and e be a bridge of G. Then ^(G) = ^(G/e).
Proof. This follows immediately from Figure 13. Since e is a bridge, the arcs ci and c2
must belong to a single component, and so do the arcs ci and c'2. We have ^(G) = ^(G/e).
□
(a) G	(b) G/e
Figure 13: The medial graphs of G and G/e.
Lemma 4.7. Let G be a ribbon graph and ei and e2 be two distinct edges of G (see Figure 4.7).
1.	If the 2-cycle given by {ei, e2 } is orientable and the common line segments of ei and e2 are adjacent as in Case 1, then ^(G) = ^(G — ei — e2).
2.	If the 2-cycle given by {ei, e2} is non-orientable and the common line segments of ei and e2 are adjacent as in Case 2, then ^(G) = ^(G/ei/e2).
3.	If ei and e2 are not parallel edges, but are incident with a common vertex of degree 2 as in Case 3, then ^(G) = ^(G/ei/e2).
646
Ars Math. Contemp. 17 (2019) 493-514
(a) Case 1
(b) Case 2
ei
e2
(c) Case 3
Figure 14: The three cases of Lemma 4.7.
Proof. We illustrate the proof with the following figures. Case 1:
Gm
G
(G - ei - e2)m
Case 2:
Gm
G
(G/e i/e2 )m
Case 3:
Gm
ei	e2
G
^_^_^
(G/ei/e2)m
Theorem 4.8. Let G be a ribbon graph. (1) If G is extremal and e is not a bridge of G, then G — e is extremal.
□
Q. Yan and X. Jin: Extremal embedded graphs
647
(2)	If G = B1 v B2 v B3 v ■ ■ ■ v Bk, then G is extremal if and only if each Bi is extremal.
(3)	If e is a bridge of G, then G/e is extremal if and only if G is extremal.
(4)	Let v be a vertex of degree 2 with exactly one adjacent vertex, the two edges joining these vertices are as in Case 1 of Lemma 4.7. Then G — v is extremal if and only if G is extremal.
(5)	Let v be a vertex of degree 2 with two different adjacent vertices x and y. Then G/{v, x}/{v, y} is extremal if and only if G is extremal.
Proof. (1): Since G is extremal, ^(G) = f (G) + y(G). By Lemma 4.1, we have
MG — e) > f (G) + y(G) — 1.
Moreover, ^(G — e) < f (G — e) + y(G — e) by Theorem 4.2 and
f (G — e) + y (G — e) = f (G) + y(G) — 1.
Therefore ^(G — e) = f (G — e) + y(G — e). Hence G — e is extremal. (2): Suppose that G is extremal. Then from Lemma 4.5 we have
k
m(G) = Y MBi) — k +1
i=1
= f (G)+ y(G)
kk
= Y f (Bi) — k + 1 + Y Y (Bi)
i=1 i=1 k
Therefore
= Y f (Bi) + Y(Bi) — k +1.
Y MBi) = Y f (Bi) + Y (Bi),
and so each Bi is extremal. The converse is proved similarly.
(3):	This follows from Lemma 4.6:
MG/e)= m(G), f (G/e) = f (G) and Y(G/e) = y(G).
(4):	This follows from Case 1 of Lemma 4.7:
m(G — v) = m(G) — 1, f (G — v) = f (G) — 1 and y (G — v) = y(G).
(5):	This follows from Case 3 of Lemma 4.7:
M(G/{v,x}/{v,y}) = M(G),	f (G/{v,x}/{v,y}) = f (G) and
Y (G/{v,x}/{v,y}) = y(G).	□
648
ArsMath. Contemp. 17(2019)591-615
5 Excluded extremal minor characterization
Definition 5.1. Let G = (V, E) be a ribbon graph and v g V and e g E. A deletion G - e or G - v of G is admissible if e is not a bridge of G or v is an isolated vertex of G; a contraction G/e or G/v is admissible if e is a bridge of G or v is a vertex of degree 2 with two different adjacent vertices u,w and G/v = G/{v,u}/{v, w}.
Definition 5.2. Let G be a ribbon graph. We say that a ribbon graph H is an extremal minor of G, denoted H -< G, if there is a sequence of ribbon graphs G = G0, Gi,..., Gt = H where for each i, Gi+i is obtained from Gi by either an admissible deletion or an admissible contraction.
Lemma 5.3. Let G be an extremal ribbon graph and H -< G. Then H is extremal.
Proof. It suffices to prove that admissible deletions and admissible contractions preserve extremity. Cases of G - e, G/e and G/v follow from Statements (1), (3), and (5) of Theorem 4.8, respectively. Let v be an isolated vertex of G. Then ^(G - v) = ^(G) - 1, f (G - v) = f (G) - 1 and 7(G - v) = 7(G). Thus if G is extremal, G - v is also extremal.	□
Lemma 5.4. Hx -< Gx if and only if H -< G.
Proof. We only need to prove the sufficiency since G = (Gx)x. Then by Definition 5.2, it suffices to prove that Lemma 5.4 holds for H = G - e and H = G - v (admissible deletions), and H = G/e and H = G/v (admissible contractions). For clarity, we denote by ex (respectively, vx ) the edge (respectively, the vertex) of Gx corresponding to the edge e (respectively, the vertex v) of G. Then e is a bridge if and only if ex is a bridge of Gx , v is an isolated vertex if and only if vx is an isolated vertex of Gx , and v is a vertex of degree 2 with two different adjacent vertices of G if and only if vx is a vertex of degree 2 with two different adjacent vertices of Gx. Hence H -< G implies Hx -< Gx.	□
Theorem 5.5. Let G be a ribbon graph. Then G is extremal if and only if it contains no extremal minor equivalent to Bi, B^, /3, % Ti or T2 (see Figure 15).
Proof. It is not difficult to obtain that
7(5?) = 7(/2x) = 1 and 7(B£) = 7(4x) = yC^) = 7(T2x) = 2.
By Theorem 4.4, Bi, /3, Ti and T2 are not extremal. It follows from Lemma 5.3 that G contains no extremal minor equivalent to Bi, B2, /3, /2, Ti or T2. To prove the converse we suppose that G is not extremal. Without loss of generality, we assume that G is connected. Then, by Theorem 4.4, y(Gx ) > 0.
Case 1: If Gx is non-orientable, then Gx contains a non-orientable cycle C. If C is odd, then C in G is orientable. The edges of G not on C can be deleted or contracted admissibly, and thus C -< G. Note that Bi -< C and hence Bi -< G, a contradiction. If C is even, then C in G is non-orientable. It follows that C -< G, /2 -< C and thus /2 ^ G, a contradiction.
Case 2: If Gx is orientable, then g(Gx) > 1.
Step 1: If f (Gx) > 1, we can take an edge e of Gx whose two edge line segments belong to different boundary components of Gx. Such an edge e must be not a bridge, we can
Q. Yan and X. 
Jin: Extremal embedded graphs
649
(a) Bi
(b) B2
(c) h
(d) In
(e) Ti
(f) Tn
Figure 15: The "forbidden" minors in Theorem 5.5.
delete it in Gx. Deleting such an e will decrease boundary component number by 1 and preserve orientability and the genus. Repeat Step 1 we obtain an orientable ribbon graph (Gx)' with f ((Gx)') = 1 and g((Gx)') = g(Gx).
Step 2: If g((Gx)') > 1, (Gx)' must have non-bridges. Take a non-bridge e of (Gx)', deleting e will preserve orientability and connectedness, and must increase boundary components by 1 since f ((Gx)') = 1 and hence decrease the genus by 1.
Now go to Step 1. Then carry out Step 2 if the genus is greater than 1. Repeat above process, finally we obtain an orientable ribbon graph (Gx)'' with f ((Gx)'') = 1 and g((Gx)'') = 1. Note that (Gx)'' ^ Gx and (Gx)'' has the cyclomatic number 2. After contracting all bridges and vertices of degree 2 with two distinct adjacent vertices in (Gx)'', we obtain four possible (Gx)''' as shown in Figure 16. Note that ax, bx, cx and dx in Figure 16 are B^, T1, Tn and I3, respectively. By Lemma 5.4, we have B^ ^ G, I3 ^ G, T1 ^ G or T2 ^ G, a contradiction.	□
650
Ars Math. Contemp. 17 (2019) 493-514
As a corollary, we obtain an excluded extremal minor characterization of extremal plane graphs. We need the following lemma and leave its proof to readers.
Lemma 5.6. If H ^ G, then 7 (H ) < 7 (G).
Corollary 5.7. A plane graph G is extremal if and only if it contains no extremal minor equivalent to Bi or I3.
Proof. By Lemma 5.6, an extremal plane graph can not contain B2, %, Ti and T2 as extremal minors. It then follows from Theorem 5.5.	□
6 Two conjectures and their generalizations
We first prove Conjecture 1.2 holds for any extremal cellularly embedded graphs on orientable surfaces.
Theorem 6.1. If G is an orientable extremal ribbon graph, then G is bipartite.
Proof. By Theorem 4.4, 7(Gx ) = 0 which implies that Gx is a plane graph and thus orientable. If G is not bipartite, then it contains an odd cycle C. C, as a subgraph of the orientable ribbon graph G, is also orientable which will become a non-orientable cycle of Gx .It follows that Gx is non-orientable, a contradiction.	□
This theorem is not true for non-orientable extremal ribbon graphs. For example, the non-orientable loop, as in Figure 3, is extremal, but not bipartite. By Theorem 6.1, any orientable extremal ribbon graph with non-zero Euler genus (including the Gx in Example 3.3) is a counterexample of the second claim of Proposition 3.2. To show that Conjecture 1.1 holds for any extremal cellularly embedded graphs we need the following lemma.
Lemma 6.2. Let G be a ribbon graph. If Gx is orientable, then Gm has an all-crossing direction such that each of the edges of G is a d-edge.
Proof. Since Gx is orientable, it follows that Gx can be drawn on the plane such that each of its edge discs is untwisted. We orient each edge disc anticlockwise as illustrated in Figure 17(a). Note that straight-ahead walks of Gm correspond exactly to boundary components of Gx. Then Gm is oriented in Figure 17(b) as boundary components of Gx. This is an all-crossing direction such that each of the edges of G is a d-edge.	□
(a) Orient each edge disc anticlockwise.	(b) Get an all-crossing direction of G,
and e is a d-edge.
m
Figure 17: The all-crossing direction of G
m-
Q. Yan and X. Jin: Extremal embedded graphs
651
Theorem 6.3. If G is an extremal ribbon graph, then each face of G is even.
Proof. Since G is an extremal ribbon graph, it follows that 7(Gx) = 0 by Theorem 4.4, and thus Gx is orientable. By Lemma 6.2, Gm has an all-crossing direction such that each of the edges of G is a d-edge. Since each edge is d-edge, we call one of edge line segments in-edge line segment if two marking arrows are all "in" arising from the all-crossing direction of Gm. Otherwise, we call the other out-edge line segment, as in Figure 18(a). It is immediate that the in-edge line segments and out-edge line segments are alternating in the every face boundary of G, as in Figure 18(b). It follows that each face of G is even. □
References
[1]	B. Bollobas and O. Riordan, A polynomial of graphs on surfaces, Math. Ann. 323 (2002), 81-96, doi:10.1007/s002080100297.
[2]	S. Chmutov, Generalized duality for graphs on surfaces and the signed Bollobas-Riordan polynomial, J. Comb. Theory Ser. B 99 (2009), 617-638, doi:10.1016/j.jctb.2008.09.007.
[3]	M. Chudnovsky, G. Kalai, E. Nevo, I. Novik and P. Seymour, Bipartite minors, J. Comb. Theory Ser. B 116 (2016), 219-228, doi:10.1016/j.jctb.2015.08.001.
[4]	J. A. Ellis-Monaghan and I. Moffatt, Graphs on Surfaces, SpringerBriefs in Mathematics, Springer, New York, 2013, doi:10.1007/978-1-4614-6971-1.
[5]	T. Endo, The link component number of suspended trees, Graphs Combin. 26 (2010), 483-490, doi:10.1007/s00373-010-0936-7.
[6]	J. L. Gross and T. W. Tucker, Topological Graph Theory, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, New York, 1987.
[7]	S. Huggett and I. Tawfik, Embedded graphs whose links have the largest possible number of components, Ars Math. Contemp. 8 (2015), 319-335, doi:10.26493/1855-3974.494.88e.
[8]	X. Jin, F. Dong and E. G. Tay, Determining the component number of links corresponding to lattices, J. Knot Theory Ramifications 18 (2009), 1711-1726, doi:10.1142/s0218216509007671.
[9]	X. Jin, F. Dong and E. G. Tay, On graphs determining links with maximal number of components via medial construction, Discrete Appl. Math. 157 (2009), 3099-3110, doi: 10.1016/j.dam.2009.06.006.
652
ArsMath. Contemp. 17(2019)591-615
[10]	M. Las Vergnas, On Eulerian partitions of graphs, in: R. J. Wilson (ed.), Graph Theory and Combinatorics, Pitman, Boston, Massachusetts-London, volume 34 of Research Notes in Mathematics, 1979 pp. 62-75, proceedings of the Conference held at the Open University, Milton Keynes, May 12, 1978.
[11]	P. Martin, Remarkable valuation of the dichromatic polynomial of planar multigraphs, J. Comb. Theory Ser. B 24 (1978), 318-324, doi:10.1016/0095-8956(78)90050-3.
[12]	I. Moffatt, Excluded minors and the ribbon graphs of knots, J. Graph Theory 81 (2016), 329341, doi:10.1002/jgt.21878.
[13]	B. Mohar and C. Thomassen, Graphs on Surfaces, Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, Maryland, 2001.
[14]	E. G. Mphako, The component number of links from graphs, Proc. Edinb. Math. Soc. 45 (2002), 723-730, doi:10.1017/s0013091501000116.
[15]	T. Pisanski, T. W. Tucker and A. Zitnik, Straight-ahead walks in Eulerian graphs, Discrete Math. 281 (2004), 237-246, doi:10.1016/j.disc.2003.09.011.
[16]	H. Shank, The theory of left-right paths, in: A. P. Street and W. D. Wallis (eds.), Combinatorial Mathematics III, Springer, Berlin, volume 452 of Lecture Notes in Mathematics, 1975 pp. 42-54, doi:10.1007/bfb0069542, proceedings of the Third Australian Conference, held at the University of Queensland, St. Lucia, May 16- 18, 1974.
[17]	W. T. Tutte, A contribution to the theory of chromatic polynomials, Canadian J. Math. 6 (1954), 80-91, doi:10.4153/cjm-1954-010-9.
[18]	S. E. Wilson, Operators over regular maps, Pacific J. Math. 81 (1979), 559-568, http:// projecteuclid.org/euclid.pjm/1102 7 852 9 6.