Authors Yury Makarychev, Amir Nayyeri, Anastasios Sidiropoulos,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 13 (5), 2017, pp. 1–47
www.theoryofcomputing.org
S PECIAL ISSUE : APPROX-RANDOM 2013
A Pseudo-Approximation for
the Genus of Hamiltonian Graphs
Yury Makarychev∗ Amir Nayyeri† Anastasios Sidiropoulos‡
Received October 1, 2013; Revised May 15, 2017; Published August 31, 2017
Abstract: The genus of a graph is a basic parameter in topological graph theory that has
been the subject of extensive study. Perhaps surprisingly, despite its importance, the problem
of approximating the genus of a graph is very poorly understood. Thomassen (1989) showed
that computing the exact genus is NP-complete, and the best known upper bound for general
graphs is an O(n)-approximation that follows by Euler’s characteristic.
We give a polynomial-time pseudo-approximation algorithm for the orientable genus
of Hamiltonian graphs. More specifically, on input a graph G of orientable genus g and a
Hamiltonian path in G, our algorithm computes a drawing on a surface of either orientable
or non-orientable genus O(g7 ).
ACM Classification: F.2.2, G.2.2
AMS Classification: 68W25
Key words and phrases: approximation algorithms, graph genus, Hamiltonian graphs
1 Introduction
A drawing of a graph G on a surface S is an injective mapping ϕ that sends every vertex v ∈ V (G) into a
point ϕ(v) ∈ S, and every edge {u, v} into a simple curve between ϕ(u) and ϕ(v), so that the images of
A preliminary version of this paper appeared in the Proceedings of the 15th International Workshop on Approximation
Algorithms for Combinatorial Optimization Problems (APPROX 2013) [9].
∗ Supported in part by the NSF Career Award CCF-1150062.
† Supported by the NSF under Grants No. CCF 1566624 and CCF 1617951.
‡ Supported by the NSF under award CAREER 1453472 and grant CCF 1423230.
© 2017 Yury Makarychev, Amir Nayyeri, and Anastasios Sidiropoulos
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2017.v013a005
Y URY M AKARYCHEV, A MIR NAYYERI , AND A NASTASIOS S IDIROPOULOS
different edges are allowed to intersect only on their endpoints. A surface is called orientable if it can be
embedded into R3 , and non-orientable otherwise. The genus of a graph G is the minimum g ≥ 0, such
that G can be drawn on a surface of genus g. Similarly, the orientable (resp. non-orientable) genus of a
graph is the minimum genus of an orientable (resp. non-orientable) surface on which G can be drawn.
Drawing graphs on various surfaces is central to graph theory (e. g., [4, 13]), and of importance to
topology and to mathematics in general (e. g., [17]), and have been the subject of intense study. Graphs of
small genus are also of importance to computer science and engineering, since they can be used to model
a wide variety of natural objects. For further background, we refer the reader to Gross and Tucker [4] for
topological graph theory and to Hatcher [5] for algebraic topology.
Computing the genus of a graph exactly. It was shown by Thomassen that computing the orientable
genus [15], and the non-orientable genus of a graph [16], are both NP-complete problems. Deciding
whether a graph has genus 0, i. e., planarity testing, can be done in linear time by the seminal result of
Hopcroft and Tarjan [6]. Filotti et al. [3] were the first to obtain an algorithm for computing a drawing of
an n-vertex graph of genus g, on a minimum-genus surface, in time nO(g) . Robertson and Seymour [14],
as part of their Graph Minor project, gave an O( f (g) · n3 ) time algorithm for determining the genus of
a graph. This was improved by a breakthrough result of Mohar [11] who gave a linear-time algorithm
for computing a minimum-genus drawing, for any fixed g. A relatively simpler linear-time algorithm
has subsequently been obtained by Kawarabayashi, Mohar and Reed [7]. The running time of the above
algorithms is exponential in g.
Approximating the genus of a graph. Perhaps surprisingly, the problem of approximating the genus
of a graph is very poorly understood. In general, the genus of a graph can be as large as Ω(n2 ) (e. g., for
the complete graph Kn ). By Euler’s characteristic, there is a trivial O(1)-approximation for sufficiently
dense graphs (i. e., of average degree at least 6 + ε, for some fixed ε > 0). For graphs of bounded degree,
√
Chen, Kanchi, and Kanevsky [2] described a simple O( n)-approximation, which follows by the fact that
graphs of small genus have small balanced vertex-separators. Following the present paper, Chekuri and
Sidiropoulos [1] obtained a polynomial-time algorithm which, given a graph G of bounded degree and of
genus g, outputs a drawing on a surface of genus O(g12 log19/2 n). Combined with the result of Chen et al.,
this implies a n1/2−α approximation for bounded-degree graphs, for some constant α > 0. Subsequently,
Kawarabayashi and Sidiropoulos [8] obtained a polynomial-time algorithm that computes a drawing on
a surface of genus O(g256 log189 n) for general graphs (that is, without the condition that the maximum
degree is bounded). Combined with Euler’s characteristic, this also implies a O(n1−β )-approximation
for general graphs, for some constant β > 0. We also remark that better bounds are known for 1-apex
graphs [12, 8] (that is, graphs that can be made planar by removing a single vertex).
Our results. We present a pseudo-approximation algorithm for the orientable genus of Hamiltonian
graphs.1 More specifically, we obtain a polynomial-time algorithm which, given a graph G and a
Hamiltonian path P in G, computes a drawing of G on a surface of either orientable or non-orientable
genus O(g7 ), where g is the orientable genus of G. The dependence of the running time is polynomial in
1 We use the term pseudo-approximation to denote the fact that even though we approximate the orientable genus of the input
graph, the output surface is allowed to be non-orientable. In this paper, we call a graph Hamiltonian if it has a Hamiltonian path.
T HEORY OF C OMPUTING, Volume 13 (5), 2017, pp. 1–47 2
A P SEUDO -A PPROXIMATION FOR THE G ENUS OF H AMILTONIAN G RAPHS
both g and n. Combined with the simple O(n/g)-approximation described above, our result immediately
gives a O(n6/7 )-pseudo-approximation for the orientable genus of graphs with a known Hamiltonian path.
These bounds are significantly stronger than the approximation guarantee achieved for general graphs [8].
We note that the algorithm for bounded-degree graphs given in [1] is not applicable in our setting, since
we are dealing with graphs of unbounded degree. The following summarizes our main result.
Theorem 1.1. There exists a polynomial-time algorithm, which, given a graph G of orientable genus g
and a Hamiltonian path P in G, outputs a drawing of G on a surface of either orientable or non-orientable
genus O(g7 ). The running time is polynomial in n and g.
1.1 Overview
In this section, we present a very informal and somewhat imprecise overview of our algorithm. We are
given a Hamiltonian graph G of genus g and a Hamiltonian path P in G. Our high-level approach is to
cover the graph G by O(g) subgraphs of constant genus, then independently draw each of them on a
surface of small genus and finally combine all drawings. More precisely, our algorithm consists of the
following steps:
Step 1: Cover G by O(g) toroidal subgraphs G1 , . . . , Gk .
Step 2: For each pair of graphs Gi , G j , compute a drawing of Gi ∪ G j .
Step 3: Combine the drawing of all pairs Gi ∪ G j , to obtain a drawing of G.
Step 1: Greedy band covering. The goal in this step is to cover G by O(g) toroidal graphs. Fix an
optimal drawing of G on a surface of genus g. Let us say that an edge e ∈ E(G) \ E(P) is global if after
contracting P, e becomes a noncontractible loop. Otherwise, we say that e is local. We can show that G
can be covered by a collection of toroidal graphs G∗1 , . . . G∗k , k = O(g), such that every local edge appears
in exactly one G∗i , and every global edge appears in exactly two graphs G∗i , G∗j . Roughly speaking, we
walk along the path, and we find maximal edge-disjoint subpaths Q1 , . . . , Qk in P, such that all edges on
either side of each Qi are homotopic (after contracting P). See Figure 1 for an example; for clarity, local
edges are omitted from the figure.
Figure 1: A greedy band covering.
Although, we do not have access to the optimal embedding of G, we still can compute such a covering
G1 , . . . , G` , for some ` = O(g). We refer to the graphs G1 , . . . , G` as elementary bands. Of course, this
T HEORY OF C OMPUTING, Volume 13 (5), 2017, pp. 1–47 3
Y URY M AKARYCHEV, A MIR NAYYERI , AND A NASTASIOS S IDIROPOULOS
means that the elementary bands G1 , . . . , G` we compute might differ from G∗1 , . . . , G∗k . This introduces
certain complications as we explain in Section 2.
Step 2: Drawing a pair of bands. Even though we have O(g) graphs Gi and each of them has genus
at most 1, we cannot naively combine their drawings. Roughly speaking, the problem is that graphs Gi
share global edges: the way an edge e is drawn in the drawing of Gi may be inconsistent with the way it is
drawn in the drawing of G j . This can happen because in Step 1, when we greedily compute the covering
by elementary bands, we can only keep track of the local edges in the current band. As a result, when
we try to combine the drawings of two bands, the local edges can introduce conflicts between the two
drawings. Figure 2 depicts an example of such a conflict. In this example, the graph G is covered by two
Figure 2: Edge conflicts in the greedy cover.
toroidal (in fact, planar) graphs G1 , G2 . However, in the drawing of G1 , all global edges are drawn on one
side of P, while in the drawing of G2 the global edges alternate between the two sides of P. We overcome
this obstacle by showing that, roughly speaking, for every pair of bands Gi , G j , there are drawings that
are nearly consistent. This is a technical part of the paper, and we refer the reader to Section 5. We just
note here that, at the high level, we decompose each band into gO(1) subgraphs, such that each subgraph
has a certain structure allowing us to find a drawing on a surface of genus gO(1) in polynomial time.
Step 3: Combining the drawings of all pairs. In this last step we combine the drawings of all pairs
of bands into a drawing of G. The key idea is that for every pair Gi ∪ G j , we can modify its drawing, such
that the global edges that are shared between either Gi , or G j , and some other elementary band G` , are
contained in a small number of homotopy classes (after contracting P). Intuitively, this means that we can
combine the drawings of all pairs by introducing a small number of “interface” handles between them. A
precise definition appears in Section 7.
1.2 Why a pseudo-approximation?
Our current algorithm is a pseudo-approximation, which means that given a graph G of orientable genus
g, it outputs a drawing on a surface of either orientable, or non-orientable genus gO(1) . However, we
believe that our approach can be generalized to obtain a (true) approximation algorithm. That is, given
a graph of genus g, compute a drawing on a surface of genus gO(1) , with the same orientability type as
G. Doing so, requires an extension of the definition of an elementary band, to account for graphs that
can be drawn on the projective plane (i. e., elementary bands of non-orientable genus at most 1). This
T HEORY OF C OMPUTING, Volume 13 (5), 2017, pp. 1–47 4
A P SEUDO -A PPROXIMATION FOR THE G ENUS OF H AMILTONIAN G RAPHS
small modification causes the number of different types of elementary bands to grow by a constant factor.
Unfortunately, as a consequence, the (already lengthy) case analysis in the proof becomes dauntingly
long. The rest of our proof remains essentially unchanged. We are not aware of a way to simplify this
case analysis, so in the interest of clarity we have decided to omit it from the present paper.
1.3 Organization
In Section 2, we show how to find the elementary band covering. The proof of the main technical step
required for Section 2 is given in the subsequent two sections. Section 3 introduces the main notions
used in the proof, and Section 4 presents the main case analysis required for the proof. In Section 5, we
explain how to combine two drawings, by decomposition into smaller subgraphs; the drawing of these
subgraphs is described in Section 6. In Section 7, we put the all pieces of our algorithm together, and
show how to find a drawing of a Hamiltonian graph.
2 Band coverings of Hamiltonian graphs
In this section, we describe a greedy algorithm that partitions the input graph to a set of O(g) simple
toroidal graphs, which we call bands. One of the tools that we have developed for this section is based on
the notion of ribbons and petals. Intuitively, ribbons and petals describe minimal topological subspaces
that contain the edges of a band.
Definition 2.1 (Bands in Hamiltonian graphs). Let G be a graph, and let P be a Hamiltonian path in G.
Let B ⊆ E(G) \ E(P). Then, B is called a band. Let Q be a subpath of P, such that every edge e ∈ B has
at least one endpoint in V (Q). We also say that B has spine P, and primary segment Q. An edge in B is
called global if exactly one of its endpoints is in V (Q); it is called local if both of its endpoints are in
V (Q). Note that every set B ⊆ E(G) \ E(P) is a band with spine P, and primary segment P.
Definition 2.2 (Elementary bands). Let G be a graph, and let P be a Hamiltonian path in G. Let
B ⊆ E(G) \ E(P) be a band with spine P, and primary segment Q ⊆ P. We define the following types of
bands, which we refer to as elementary.
Type-1. We say that B is of type-1 (see Figure 3(a)) if the following conditions are satisfied. There
exist subpaths P1 , P2 , P3 , P4 ⊂ P, with P1 , P2 , P3 , P4 , Q being pairwise edge-disjoint, and such that
the set M of global edges in B can be decomposed into M = M1 ∪ M2 ∪ M3 ∪ M4 , such that for
every i ∈ {1, . . . , 4}, every edge in Mi has one endpoint in V (Q), and one in V (Pi ). Moreover, there
exists a planar drawing ϕ of the graph H = B ∪ Q ∪ P1 ∪ . . . ∪ P4 , satisfying the following. For every
i ∈ {1, . . . , 4}, ϕ(Pi ) lies in the outer face of ϕ, and all the curves ϕ(e), e ∈ Mi , are attached to the
same side of ϕ(Pi ). We say that the paths P1 , . . . , P4 are the outlets of B.
Type-2. We say that B is of type-2 (see Figure 3(b)) if the following conditions are satisfied. There exist
subpaths P1 , P2 , P3 ⊂ P, with P1 , P2 , P3 , Q being pairwise edge-disjoint, and such that the set M of
global edges in B can be decomposed into M = M1 ∪ M2 ∪ M3 , such that for every i ∈ {1, 2, 3},
every edge in Mi has one endpoint in V (Q), and one in V (Pi ). Moreover, there exists a planar
drawing ϕ of the graph H = B ∪ Q ∪ P1 ∪ P2 ∪ P3 , satisfying the following. If we denote by ϕ 0 the
T HEORY OF C OMPUTING, Volume 13 (5), 2017, pp. 1–47 5
Y URY M AKARYCHEV, A MIR NAYYERI , AND A NASTASIOS S IDIROPOULOS
(a) Type-1. (b) Type-2.
Figure 3: The different types of elementary bands. The primary segment is in bold.
drawing induced by ϕ on H \V (P3 ), then for every i ∈ {1, 2}, ϕ 0 (Pi ) lies in the outer face. Also,
there exists v ∈ V (P3 ), such that ϕ(v) also lies in the outer face. Moreover, for every i ∈ {1, 2}, all
the curves ϕ(e), e ∈ Mi , are attached to the same side of ϕ(Pi ). Note that the curves ϕ(e), e ∈ M3
are allowed to be attached to both sides of ϕ(P3 ). We say that the paths P1 , and P2 are the outlets of
B, and that the path P3 is the double outlet of B.
We say that ϕ is a canonical drawing of B (or a canonical drawing of H, when B is clear from the context).
For an elementary band of type-2, we can pick ϕ so that the curves ϕ(Q), ϕ(P1 ), ϕ(P2 ), ϕ(P3 ) become
segments of a horizontal line `, with ϕ(Q) appearing to the left of ϕ(P3 ). We call ` the canonical line of
ϕ. Let ≺ be the total ordering of V (Q) ∪V (P3 ) induced by a left-to-right traversal of `. We say that ≺
is the canonical ordering of ϕ. We extend ≺ to B as follows. Let {x, y}, {x0 , y0 } ∈ B, with x, x0 ∈ V (Q).
Then, we define {x, y} ≺ {x0 , y0 } if either x ≺ x0 , or (x = x0 ) ∧ (y ≺ y0 ). Since G does not contain any
parallel edges, it follows that ≺ is a total ordering of B.
We remark that a band can be of both type-1 and type-2 (e. g., the trivial band). Figure 3 depicts
examples of type-1 and type-2 elementary bands.
Definition 2.3 (Band coverings for Hamiltonian graphs). Let G be a graph, and let P be a Hamiltonian
path in G. A band covering with spine P for G is a collection B = {(Bi , Qi )}ti=1 satisfying the following
conditions:
1. For every i ∈ {1, . . . ,t}, Bi is an elementary band with spine P, and primary segment Qi .
i∈{1,...,t} Bi = E(G) \ E(P).
S
2.
3. For every i 6= j ∈ {1, . . . ,t}, we have V (Qi ) ∩V (Q j ) = 0.
/
We remark that every edge in E(G) \ E(P) is contained in at least one, and at most two bands in the band
covering B. If it is contained in exactly one band, then we say that it is local, and otherwise we say that it
is global.
First we show that a band covering that is composed of O(g) bands exists. The intuition behind this
proof comes from looking at the homotopy classes of the edges in E(G) \ P in an optimal embedding.
Moreover, we show that we can compute a band covering of size O(g). Note that this band covering that
T HEORY OF C OMPUTING, Volume 13 (5), 2017, pp. 1–47 6
A P SEUDO -A PPROXIMATION FOR THE G ENUS OF H AMILTONIAN G RAPHS
we compute is not necessarily optimal. However, its size is within a constant factor of the optimal band
covering size. The main tool that our algorithm uses is a so-called ribbon-petal covering. See Section 3
for the description of ribbon petal covering and the proof of the following lemmas.
Lemma 2.4 (Existence of a small band covering). Let G be a graph of orientable genus g, and P a
Hamiltonian path in G. Then, there exists a band covering B = {(Bi , Qi )}ti=1 , with spine P for G, with
t = O(g).
The proof of the above Lemma is rather lengthy, and is presented in the next two sections. Assuming
Lemma 2.4, we can now prove the main result of this section.
Lemma 2.5 (Computing a small band covering). Let G be a graph of orientable genus g, and P a
Hamiltonian path in G. Then, given G and P, we can compute in polynomial time a band covering for G
with spine P, of size O(g).
Proof. Fix an ordering ≺ of V (P), induced by a traversal of P. We inductively define a partition of P into
/ For i ≥ 1, given Q0 , . . . , Qi−1 , we inductively
vertex disjoint subpaths Q1 , . . . , Qt as follows. Let Q0 = 0.
define Qi to be the maximal prefix (with respect to ≺) of P \ i−1
S
j=0 Qi , such that if we set
Bi = {{u, v} ∈ E(G) \ E(P) : {u, v} ∩V (Qi ) 6= 0}
/ ,
then Bi is an elementary band with spine P, and primary segment Qi .
Finally, we set t to be the smallest integer such that V (P) \ tj=1 V (Q j ) = 0.
S
/ It is straightforward to
check that B is a band covering for G with spine P. It is also clear that B can be computed in polynomial
time.
0
It remains to bound |B| = O(g). By Lemma 2.4 there exists a band covering B0 = {(B0i , Q0i )}ti=1 for G,
with t 0 = O(g). Since for every i ∈ {1, . . . ,t} we pick a maximal prefix Qi such that Bi is an elementary
with spine P, and primary segment Qi , it follows that ij=1 V (Qi ) ⊇ ij=1 V (Q0i ). Therefore, t ≤ t 0 = O(g),
S S
as required.
3 Ribbons and petals
In this section we define a decomposition of an embedded graph into a small collection of topologically
simpler subgraphs.
Definition 3.1 (Ribbon). Let γ be a simple open curve in a surface F. A set A ⊂ F is called a γ-ribbon if
it satisfies one of the following conditions:
1. The set A is the image of a simple curve with endpoints x, y ∈ γ, and such that A ∩ γ = {x, y}.
2. Intuitively, A is a deformed triangle in F that intersects γ only on a vertex and its opposite edge.
Formally, let T be 2-simplex, let a be a vertex of T , and let ` be the edge of T opposite to a. Then,
there exists a continuous mapping f : T → F such that f is a homeomorphism on T \ {a}, and on `.
Moreover,
f (a ∪ `) ⊆ γ , f (T \ (a ∪ `)) ∩ γ = 0/ , and f (T ) = A .
T HEORY OF C OMPUTING, Volume 13 (5), 2017, pp. 1–47 7
Y URY M AKARYCHEV, A MIR NAYYERI , AND A NASTASIOS S IDIROPOULOS
(a) Examples of sets A that are γ-ribbons. (b) Not a γ-ribbon.
Figure 4: Ribbons.
Figure 5: From left to right: A single γ-petal, a double γ-petal, and a triple γ-petal X.
3. Intuitively, A is a deformed rectangle in F that intersects γ only on two opposite edges. Formally,
there exists an f : [0, 1]2 → F be a continuous mapping such that f is a homeomorphism on
(0, 1) × [0, 1], on {0} × [0, 1], and on {1} × [0, 1]. Moreover,
f ((0, 1) × [0, 1]) ∩ γ = 0/ , f ({0, 1} × [0, 1]) ⊆ γ , and f ([0, 1]2 ) = A .
We say that the points f ((0, 0)), f ((0, 1)), f ((1, 0)), f ((1, 1)) are endpoints of A. Figure 4(a) depicts
examples of ribbons.
Definition 3.2 (Petal). Let γ be a simple open curve in a surface F. A set X ⊂ F is called a γ-petal if
there exists a continuous mapping f : [0, 1]2 → F, so that f is a homeomorphism on [0, 1] × (0, 1], with
f ((0, 1] × [0, 1]) ∩ γ = 0/ , f ({0} × [0, 1]) ⊆ γ , and f ([0, 1]2 ) = X .
We distinguish between the following three types of petals:
Single. The γ-petal X is called single if f is a homeomorphism on [0, 1]2 .
Double. The γ-petal X is called double if it is not single, and if there exists x ∈ [0, 1], so that f is a
homeomorphism on {0} × [0, x], and on {0} × [x, 1].
Triple. The γ-petal X is called triple if it is not single, and it is not double, and if there exist x < y ∈ [0, 1],
so that f is a homeomorphism on {0} × [0, x], on {0} × [x, y], and on {0} × [y, 1].
We say that the points f ((0, 0)), and f ((0, 1)) are endpoints of X. Figure 5 depicts examples of the three
different types of petals.
Definition 3.3 (Ribbon-petal covering). Let G be a graph of genus g, and let P be a Hamiltonian path in
G. Let ϕ be a drawing of G on a surface S of genus g. Let X be a collection of subsets of S. Then, we say
that X is a ribbon-petal covering for (G, P, ϕ), if the following conditions are satisfied:
T HEORY OF C OMPUTING, Volume 13 (5), 2017, pp. 1–47 8
A P SEUDO -A PPROXIMATION FOR THE G ENUS OF H AMILTONIAN G RAPHS
1. Every X ∈ X is either a ϕ(P)-ribbon, or a ϕ(P)-petal.
2. For every X, X 0 ∈ X, with X 6= X 0 , we have X ∩ X 0 ⊆ ϕ(P).
3. For every e ∈ E(G) \ E(P), there exists X ∈ X, such that ϕ(e) ⊆ X.
Lemma 3.4 (Malnič and Mohar [10]). Let M be an orientable surface of genus g, and let x ∈ M. Let X
be a collection of noncontractible simple loops such that for every C,C0 ∈ X, we have C ∩C0 = x. Suppose
that all curves in X are pairwise nonhomotopic with respect to the basepoint x (i. e., in π1 (M, x)). Then,
|X| ≤ 6g − 3.
Lemma 3.5. Let G be a graph of genus g, and let P be a Hamiltonian path in G. Let ϕ be a drawing of G
on a surface S of genus g. For every e ∈ E(G) \ E(P), let Pe be the subpath of P between the endpoints of
e, and define the cycle Ce = Pe ∪ {e}; let also γe be the loop obtained from ϕ(Ce ) by contracting ϕ(P) to
the basepoint. Let E ∗ = {e ∈ E(G) \ E(P) : γe is non-contractible in S}. Let X ⊆ E ∗ , such that for every
e 6= e0 ∈ X, the cycles γe and γe0 are non-homotopic. Then, |X| ≤ 6g − 3.
Proof. Let S0 be the surface obtained from S by contracting ϕ(P) to a single point. Let G0 be the graph
obtained from G by contracting P to a single vertex p, and thus G0 is drawn on a surface of genus g. The
assertion now follows immediately by Lemma 3.4.
Lemma 3.6 (Existence of small ribbon-petal coverings). Let G be a graph of genus g, and let P be
a Hamiltonian path in G. Let ϕ be a drawing of G on a surface S of genus g. Then, there exists a
ribbon-petal covering X for (G, P, ϕ), with |X| ≤ 24g − 12.
Proof. For every e ∈ E(G) \ E(P), let Pe be the subpath of P between the endpoints of e, and define the
cycle Ce = Pe ∪ {e}; let also γe be the loop obtained from ϕ(Ce ) by contracting ϕ(P) to the basepoint. Let
E ∗ = {e ∈ E(G) \ E(P) : γe is non-contractible in S} .
Consider the partition E ∗ = Y1 ∪ . . . ∪Yk , such that for every i ∈ {1, . . . , k}, for every e, e0 ∈ Yi , the loops
γe and γe0 are homotopic, and for every i 6= j ∈ {1, . . . , k}, for every e ∈ Yi , e0 ∈ Y j , the loops γe and γe0 are
non-homotopic. By Lemma 3.5, we have k ≤ 6g − 3.
Let i ∈ {1, . . . , k}. Since for all e ∈ Yi , all the loops γe , e ∈ Yi are homotopic, it follows that there
exists an ordering e1 , . . . , eki of the edges in Yi , and a continuous mapping fi : [0, 1]2 → S, with fi ([0, 1] ×
{0, 1}) ⊆ ϕ(P), and moreover for every e j ∈ Yi , there exists x j ∈ [0, 1], so that fi (x j × [0, 1]) = ϕ(e j ).
Since for every i0 6= i ∈ {1, . . . , k} and for every e ∈ Yi , e0 ∈ Yi0 , the loops γe and γe0 are non-homotopic,
it follows that we can pick the maps f1 , . . . , fk so that for every i 6= i0 ∈ {1, . . . , k} the sets fi ([0, 1]2 )
and fi0 ([0, 1]2 ) have disjoint interiors. It therefore suffices to show how every set Ai = fi ([0, 1]2 ) can
be decomposed into at most three ϕ(P)-ribbons with disjoint interiors. To that end, we consider the
following cases: Let a, b be the two endpoints of ϕ(P).
1. If fi ([0, 1] × {0}), and fi ([0, 1] × {1}) are both single points, then the set fi ([0, 1]2 ) is clearly a
ϕ(P)-ribbon.
T HEORY OF C OMPUTING, Volume 13 (5), 2017, pp. 1–47 9
Y URY M AKARYCHEV, A MIR NAYYERI , AND A NASTASIOS S IDIROPOULOS
2. If fi ([0, 1] × {0}) is a single point, and fi ([0, 1] × {1}) is not a single point, then we can pick fi
so that there exist at most two values x < y ∈ [0, 1] such that for every z ∈ [0, 1] \ {x, y}, we have
f ((z, 1)) ∈
/ {a, b}. It follows that the sets fi ([0, x] × [0, 1]), fi ([x, y] × [0, 1]), fi ([y, 1] × [0, 1]) are
the desired ϕ(P)-ribbons.
3. If fi ([0, 1] × {0}) is not a single point, and fi ([0, 1] × {1}) is a single point, we can decompose
fi ([0, 1]2 ) into at most three ϕ(P)-ribbons as in the previous case.
4. If fi ([0, 1] × {0}) is not a single point, and fi ([0, 1] × {1}) is not a single point, then we can pick fi
so that there exist at most two values x < y ∈ [0, 1] such that for every z ∈ [0, 1] \ {x, y}, we have
f ((z, 1)) ∈/ {a, b}, and f ((z, 0)) ∈
/ {a, b}. It follows that the sets fi ([0, x] × [0, 1]), fi ([x, y] × [0, 1]),
fi ([y, 1] × [0, 1]) are the desired ϕ(P)-ribbons.
We perform the above decomposition to each set fi ([0, 1]2 ), i ∈ {1, . . . , k}.
For every e ∈ E(G) \ (E(P) ∪ E ∗ ), the cycle ϕ(Ce ) is contractible in S. Therefore, it bounds a disk
De ⊂ S, and this disk is a ϕ(P)-petal. Let e, e0 ∈ E ∗ . Since ϕ(e) ∩ ϕ(e0 ) ⊂ ϕ(P), we have that either
De ⊂ De0 , or De0 ⊂ De , or De ∩ De0 ⊂ ϕ(P). It follows that we can cover all the disks {De }e∈E(G)\E ∗ by
using at most one ϕ(P)-petal between every two consecutive ribbons on every side of ϕ(P), and possibly
one more ϕ(P)-petal for every one of the two endpoints of ϕ(P). Since every ribbon intersects ϕ(P) in at
most two segments, in total we obtain a collection of at most k petals satisfying the assertion.
4 From ribbons and petals to bands
In this section we show that a ribbon-petal covering can be used to cover the graph with a small number
of elementary bands.
Lemma 4.1. Let G be a graph, and let P be a Hamiltonian path in G. Let v ∈ V (P), and let
B = {{x, y} ∈ E(G) \ E(P) : x = v, or y = v} .
Then, B is an elementary band of type-1, with spine P, and primary segment v.
Proof. Let R1 , R2 be the two connected components of P − v, where any of R1 , and R2 , can be empty.
Then, it is immediate to check that B is an elementary band of type 1, with primary segment v, by setting
in Definition 2.2(Type-1) P1 = P \ R2 , and P2 = R2 .
Lemma 4.2 (From ribbons and petals to bands). Let G be a graph, and let P be a Hamiltonian path in
G. Let ϕ be a drawing of G on an orientable surface S. Let X be a ribbon-petal covering for (G, P, ϕ).
Let A be the set of all points that are endpoints of all the ribbons, and all the petals in X. Recall that all
these points lie in ϕ(P). Let p, q be the endpoints of the curve ϕ(P). Let p1 , . . . , pt be the ordering of the
points in A ∪ {p, q} induced by a traversal of ϕ(P). Let i ∈ {1, . . . ,t − 1}, and let α be the segment of
ϕ(P) between pi , and pi+1 . Let
B = {e ∈ E(G) \ E(P) : ϕ(e) ∩ α 6= 0}.
/
Let also Q be the maximal subpath of P such that ϕ(Q) ⊆ α. Then, there exists k ≤ 3, so that the following
conditions are satisfied:
T HEORY OF C OMPUTING, Volume 13 (5), 2017, pp. 1–47 10
A P SEUDO -A PPROXIMATION FOR THE G ENUS OF H AMILTONIAN G RAPHS
Sk
1. There exist pairwise vertex-disjoint subpaths Q1 , . . . , Qk ⊆ Q, such that V (Q) = i=1 V (Qi ).
2. There exist pairwise disjoint subsets B1 , . . . , Bk ⊆ B, such that for any j ∈ {1, . . . , k}, B j is an
elementary band with spine P, and with primary segment Q j .
Proof. For any pair of points x, y ∈ ϕ(P), let λ [x, y] be the segment of ϕ(P) between x, and y. Let also
λ [x, y) = λ [x, y] \ {y}, λ (x, y] = λ [x, y] \ {x}, and λ (x, y) = λ [x, y] \ {x, y}. Let P[x, y] denote the maximal
subpath P0 ⊆ P, such that ϕ(P0 ) is contained in λ [x, y]. Let B[x, y] be the subset of edges in B with at least
one endpoint in V (P([x, y]). Define similarly P[x, y), P(x, y], P(x, y), B[x, y), B(x, y], and B(x, y).
Let ≺ be the total ordering of the points in the curve ϕ(P) induced by a traversal of ϕ(P), with
p1 ≺ · · · ≺ pt .
We consider the following cases. (For the sake of clarity, in the accompanying figures, we only draw
the global edges of the resulting bands.)
Case 1: There exists a double ϕ(P)-petal X ∈ X, such that both sides of α are in X. Assume w.l.o.g. that
pi is an endpoint of ϕ(P), and pi+1 is an endpoint of X. Let also r be the other endpoint of X.
Then, B is an elementary band of type-1, with primary segment Q, and outlet P[pi+1 , r].
Case 2: There exists a triple ϕ(P)-petal X ∈ X, such that both sides of α are in X. Assume w.l.o.g. that
pi is an endpoint of ϕ(P), and pi+1 is an endpoint of X. Let also r be the other endpoint of ϕ(P).
Then, B is an elementary band of type-2, with primary segment Q, and double outlet P[pi+1 , r].
T HEORY OF C OMPUTING, Volume 13 (5), 2017, pp. 1–47 11
Y URY M AKARYCHEV, A MIR NAYYERI , AND A NASTASIOS S IDIROPOULOS
Case 3: There exists a ϕ(P)-petal X ∈ X, and a single ϕ(P)-petal Y ∈ X, such that one side of α is in X,
and the other is in Y . The cases where X is a single, or a double ϕ(P)-petal are special sub-cases of
the case where X is a triple ϕ(P)-petal. It therefore suffices to consider the latter case. Let p j , pl ,
with j ≤ i < i + 1 ≤ l be the endpoints of X.
Let r ∈ V (P[pi , pi+1 ]) be minimal with respect to ≺ such that all edges in B(r, pi+1 ] that have an
endpoint in P[p1 , p j ], are incident to P[p, p j ] on the same side as Y is incident to P. Similarly,
let s ∈ V (P[pi , pi+1 ]) be maximal with respect to ≺ such that all edges in B(pi , s] that have an
endpoint in P[pl , q], are incident to P[pl , q] on the same side as Y is incident to P. Then, B[pi , r) is
an elementary band of type-1, with primary segment Q[pi , r), and outlets P[p, pi ], and P[r, pi+1 ].
Also, B(r, s) is an elementary band of type-1, with primary segment Q(r, s), and outlets P[p, pi ],
P[pi , r], P[s, pi+1 ], and P[pi+1 , q]. Also, B(s, pi+1 ) is an elementary band of type-1, with primary
segment Q(s, pi+1 ), and outlets P[pi , s], and P[pi+1 , q].
Case 4: There exists a triple ϕ(P)-petal X ∈ X, and a ϕ(P)-ribbon Y ∈ X, such that one side of α is in
X, and the other is in Y . This case is identical to Case 3.
Case 5: There exists either a single, or a double ϕ(P)-petal X ∈ X, and a ϕ(P)-ribbon Y ∈ X, such that
one side of α is in X, and the other is in Y . The case where X is a single ϕ(P)-petal is a special case
of the case where X is a double ϕ(P)-petal. We can therefore assume w.l.o.g. that X is a double
ϕ(P)-petal. Moreover, the case were both X and Y are double ϕ(P)-petals is a special case of this
one. If Y is attached only to one side of ϕ(P), then this case is identical to Case 4 above. Therefore,
it remains to consider the case where Y is attached to both sides of ϕ(P). Let a, a0 , b, b0 ∈ S be the
endpoints of Y , and r, r0 ∈ S be the endpoints of X. We may assume w.l.o.g. that either
r a a0 r 0 b b0 , or r a r0 a0 b b0 .
Let s be the minimal point in {a0 , r0 } with respect to ≺, and let s0 be the maximal one.
T HEORY OF C OMPUTING, Volume 13 (5), 2017, pp. 1–47 12
A P SEUDO -A PPROXIMATION FOR THE G ENUS OF H AMILTONIAN G RAPHS
Then, B is an elementary band of type-2, with primary segment P[a, s], outlets P[s, s0 ], and P[b, b0 ],
and with double outlet P[p, a].
Case 6: There exists a ϕ(P)-ribbon X ∈ X, such that both sides of α are in X. Let a, a0 , b, b0 ∈ S be the
endpoints of X. We may assume w.l.o.g. that either
a b a0 b0 , or b a a0 b0 .
Let r be the minimal in {a, b}, and r0 be the maximal in {a, b}. Let also s be the minimal in {a0 , b0 },
and s0 be the maximal in {a0 , b0 }.
Then, B is an elementary band of type-1, with primary segment P[r0 , s], and outlets P[r, r0 ], and
P[s, s0 ].
Case 7: There exists a ϕ(P)-ribbon X ∈ X, and a ϕ(P)-ribbon Y ∈ X, such that one side of α is in X, and
the other is in Y . The ϕ(P)-ribbon X is attached to a single side of ϕ(P), and the ϕ(P)-ribbon Y is
also attached to a single side of ϕ(P). Let a1 , . . . , a4 ∈ S be the endpoints of X, and let b1 , . . . , b4 ∈ S
be the endpoints of Y . Assume w.l.o.g. that a1 a2 a3 a4 , and b1 b2 b3 b4 .
We consider the following subcases:
Case 7-1: Suppose that a2 ≺ b1 , and a4 ≺ b3 . Let r be the minimal with respect to ≺ in {b1 , a3 },
and let r0 be maximal in {b1 , a3 }. Similarly, let s be the minimal in {b2 , a4 }, and let s0 be the
maximal in {b2 , a4 }.
T HEORY OF C OMPUTING, Volume 13 (5), 2017, pp. 1–47 13
Y URY M AKARYCHEV, A MIR NAYYERI , AND A NASTASIOS S IDIROPOULOS
Then, B is an elementary band of type-1, with primary segment P[r0 , s], and with outlets
P[a1 , a2 ], P[r, r0 ), P(s, s0 ], and P[b3 , b4 ].
Case 7-2: Suppose that a2 ≺ b3 , and b2 ≺ a3 . Let r be the minimal with respect to ≺ in {a1 , b1 },
and let r0 be maximal in {a1 , b1 }. Similarly, let s be the minimal in {a2 , b2 }, and let s0 be
the maximal in {a2 , b2 }. Let z be the minimal in {a3 , a4 , b3 , b4 }, and let z0 be the maximal in
{a3 , a4 , b3 , b4 }. Assume w.l.o.g. that pi = r0 , and pi+1 = s.
Then, B is an elementary band of type-2, with primary segment P[r0 , s], with outlets P[r, r0 ),
P(s, s0 ], and with double outlet P[z, z0 ].
Case 7-3: Suppose that b1 a2 a3 b2 b3 a4 . Let r be the minimal with respect to ≺ in
{a1 , b1 }, and let r0 be maximal in {a1 , b1 }. Similarly, let s be the minimal in {a4 , b4 }, and let
s0 be the maximal in {a4 , b4 }. If pi = r0 , and pi+1 = a2 , then this configuration can be handled
in the same way as case of Case 7-2. So it suffices to consider the case pi = a3 , and pi+1 = b2 .
Let z be the maximal with respect to ≺ vertex in P[a3 , b2 ], such that z has an incident edge
e = {z, w}, with w ∈ V (P[r, a2 ]).
We can decompose B into three elementary bands as follows. First, B[a3 , z) is an elementary
band of type-2, with primary segment P[a3 , z), outlet P[z, s0 ], and double outlet P[r, a3 ). Next,
T HEORY OF C OMPUTING, Volume 13 (5), 2017, pp. 1–47 14
A P SEUDO -A PPROXIMATION FOR THE G ENUS OF H AMILTONIAN G RAPHS
B[z, z] is an elementary band of type-1 (by Lemma 4.1), with primary segment z. Finally,
B(z, b2 ] is an elementary band of type-2, with primary segment P(z, b2 ], outlet P[r, a3 ], and
double outlet P(b2 , s0 ].
Case 8: There exists a ϕ(P)-ribbon X ∈ X, and a ϕ(P)-ribbon Y ∈ X, such that one side of α is in X,
and the other is in Y . The ϕ(P)-ribbon X is attached to a single side of ϕ(P), and the ϕ(P)-ribbon
Y is attached to both sides of ϕ(P). Let a1 , . . . , a4 ∈ S be the endpoints of X, and let b1 , . . . , b4 ∈ S
be the endpoints of Y . Assume w.l.o.g. that a1 a2 a3 a4 , and b1 b2 b3 b4 .
We consider the following sub-cases:
Case 8-1: Suppose that X ∩Y is a contiguous segment of ϕ(P), and that the two segments where
Y intersects ϕ(P), are disjoint. Assume w.l.o.g. that X ∩Y = λ [a3 , a4 ] ∩ λ [b1 , b2 ]. Let r be
the minimal with respect to ≺ in {a3 , b1 }, and let r0 be the maximal in {a3 , b1 }. Similarly, let
s be the minimal in {a4 , b2 }, and let s0 be the maximal in {a4 , b2 }.
Then, B is an elementary band of type-1, with primary segment P[r0 , s], and with outlets
P[a1 , a2 ], P[r, r0 ), P(s, s0 ], and P[b3 , b4 ].
Case 8-2: Suppose that X ∩Y consists of two disjoint contiguous segments of ϕ(P), and that the
two segments where Y intersects ϕ(P), are disjoint. Let r be the minimal with respect to ≺ in
{a1 , b1 }, and let r0 be the maximal in {a1 , b1 }. Similarly, let s be the minimal in {a4 , b2 }, and
let s0 be the maximal in {a4 , b2 }. Assume w.l.o.g. that X ∩Y = λ [r0 , a2 ] ∪ λ [a3 , s]. We may
further assume w.l.o.g. that pi = a3 , and pi+1 = s, since all remaining cases can be handled in
the exact same way.
T HEORY OF C OMPUTING, Volume 13 (5), 2017, pp. 1–47 15
Y URY M AKARYCHEV, A MIR NAYYERI , AND A NASTASIOS S IDIROPOULOS
Then, B is an elementary band of type-2, with primary segment P[a3 , s], and with outlets
P(s, s0 ], P[b3 , b4 ], and with double outlet P[r, a3 ).
Case 8-3: Suppose that X ∩Y is a contiguous segment of ϕ(P), and that the two segments where
Y intersects ϕ(P), are not disjoint. We can assume w.l.o.g. that a1 a2 a3 b1 a4
b2 b3 b4 , since all other cases can be handled in the exact same way.
Then, B is an elementary band of type-2, with primary segment P[b1 , a4 ], and with outlets
P[a1 , a2 ], P[a3 , b1 ), and double outlet P(a4 , b4 ]. We remark that the outlets P[a1 , a2 ] and
P[a3 , b1 ] can also be merged into a single outlet.
Case 8-4: Suppose that X ∩ Y consists of two disjoint contiguous segments of ϕ(P), and that
the two segments where Y intersects ϕ(P), are not disjoint. We can assume w.l.o.g. that
a1 b1 a2 b2 b3 a3 a4 b4 , and that pi = b1 , pi+1 = a2 , since all other cases can
be handled in the exact same way.
Let z be the maximal vertex with respect to ≺ such that there exists an edge e with one
endpoint in z, and such that ϕ(e) is incident to both sides of ϕ(P). Then, B can be covered
by three elementary bands as follows. First, B[b1 , z) is an elementary band of type-1, with
primary segment P[b1 , z), and outlets P[a1 , b1 ), P[z, a2 ], P[b2 , b3 ], and P[a3 , a4 ]. Next, B[z, z]
is an elementary band of type-1, with primary segment z. Finally, B(z, a2 ] is an elementary
band of type-2, with primary segment P(z, a2 ], outlet P[a1 , z], and with double outlet P(a2 , b4 ].
T HEORY OF C OMPUTING, Volume 13 (5), 2017, pp. 1–47 16
A P SEUDO -A PPROXIMATION FOR THE G ENUS OF H AMILTONIAN G RAPHS
Case 9: There exists a ϕ(P)-ribbon X ∈ X, and a ϕ(P)-ribbon Y ∈ X, such that one side of α is in X, and
the other is in Y . The ϕ(P)-ribbon X is attached to both sides of ϕ(P), and the ϕ(P)-ribbon Y is
also attached to both sides of ϕ(P). Let a1 , . . . , a4 ∈ S be the endpoints of X, and let b1 , . . . , b4 ∈ S
be the endpoints of Y . Assume w.l.o.g. that a1 a2 a3 a4 , and b1 b2 b3 b4 .
We consider the following subcases:
Case 9-1: Suppose that X ∩ ϕ(P) consists of two disjoint segments. Assume that b2 ≺ a3 , a2 ≺ b3 ,
b1 a2 , and a1 b2 . Let r be the minimal with respect to ≺ in {a1 , b1 }, and let r0 be the
maximal in {a1 , b1 }. Let s be the minimal in {a2 , b2 }, and let s0 be the maximal in {a2 , b2 }.
Suppose that pi = r0 , and pi+1 = s.
Let z be the minimal in {a3 , b3 , a4 , b4 }, and let z0 be the maximal in {a3 , b3 , a4 , b4 }. Then,
B is an elementary band of type-2, with primary segment P[r0 , s], with outlets P[r, r0 ), and
P[s, s0 ), and with double outlet P[z, z0 ].
Case 9-2: Suppose that X ∩ ϕ(P) consists of a single disjoint segment. Assume that λ [a1 , a3 ], and
λ [a2 , a4 ] are sides of X, and that a3 b3 a4 . Let r be the minimal with respect to ≺ in
{a1 , b1 }, and let r0 be the maximal in {a1 , b1 }. Let s be the minimal in {a4 , b4 }, and let s0 be
the maximal in {a4 , b4 }. Suppose that pi = r0 , and pi+1 = s.
Let z be the maximal point in P[r0 , b2 ], such that there exists an edge e ∈ B having z as an
endpoint, and such that ϕ(e) is incident to both sides of ϕ(P). Then, B can be covered by
three elementary bands as follows. First, B[r0 , z) is an elementary band of type-1, with primary
segment P[r0 , z), and with outlets P[r, r0 ), P[z, b2 ], and P[a2 , a4 ]. Next, B[z, z] is an elementary
band of type-1, with primary segment v. Finally, B(z, b2 ] is an elementary band of type-1,
with primary segment P(z, b2 ], and with outlets P[r, z], P(b2 , a3 ], and P[b3 , b4 ].
T HEORY OF C OMPUTING, Volume 13 (5), 2017, pp. 1–47 17
Y URY M AKARYCHEV, A MIR NAYYERI , AND A NASTASIOS S IDIROPOULOS
The above cases exhaust all possibilities for the following reason: Each side of α is covered by
at most one element in X, and each such element is either a ϕ(P)-ribbon or a single, double, or triple
ϕ(P)-petal. In Cases 1 and 2, both sides of α are covered by the same ϕ(P)-petal; such a ϕ(P)-petal
must be either double (Case 1) or triple (Case 2), since single ϕ(P)-petals are attached only to one side of
ϕ(P). In Case 3, a distinct ϕ(P)-petal covers each side of α, and one of them is single; the other petal
can be either single, double, or triple, and the most general case is the one where it is triple. The case
where both sides of α are covered by double ϕ(P)-petals is a special subcase of Case 5. This exhausts
all possibilities for the cases where both sides of α are covered by ϕ-petals. In Case 4, one side of α is
covered by some ϕ(P)-petal and the other side is covered by some ϕ(P)-ribbon; If the petal is triple, then
the ribbon must be attached to a single side of ϕ(P), and thus this case can be treated as a special subcase
of Case 3. This exhausts all possibilities for the cases where one side of α is covered by a ϕ(P)-petal,
and the other by a ϕ(P)-ribbon. It remains to consider the case where both sides of α are covered by
ϕ-ribbons. In Case 6, both sides of α are covered by the same ϕ(P)-ribbon. In the remaining Cases 7–9,
each side of α is covered by a distinct ϕ(P)-ribbon; each one of these two ribbons is attached either to
a single or to both sides of ϕ(P), which leads to three possible cases. In Case 7, each one of the two
ϕ(P)-ribbons are attached to a single side of ϕ(P). In Case 8, one ϕ(P)-ribbon is attached to a single
side of ϕ(P), and the other one is attached to both sides of ϕ(P). Finally, in Case 9, both ϕ(P)-ribbons
are attached to both sides of ϕ(P). Thus every possible configuration is isomorphic to one of the cases
considered above. This concludes the proof.
We are now ready to prove the existence of small band coverings.
Proof of Lemma 2.4. Let ϕ be a drawing of G on an orientable surface S of genus g. By Lemma 3.6 there
exists a ribbon-petal covering X for (G, P, ϕ), with |X| ≤ 24g − 12. Let A be the set of all endpoints of
all ribbons, and all petals in X. Since any X ∈ X can have at most 4 endpoints, we have |A| ≤ 96g − 48.
Let p, q ∈ S be the endpoints of the curve ϕ(P), and let A0 = A ∪ p, q. Let p1 , . . . , pk be an ordering of A0
induced by a traversal of the curve ϕ(P), where k ≤ |A| + 2 ≤ 96g − 46. For any i ∈ {1, . . . , k − 1}, let αi
be the segment of ϕ(P) between pi , and pi+1 . Let also Zi be the maximal subpath of P with ϕ(Zi ) ⊆ αi .
Let
Fi = {{x, y} ∈ E(G) \ E(P) : {x, y} ∩V (Zi ) 6= 0}
/ .
By Lemma 4.2 there exists a collection {(Bi, j , Qi, j )}kj=1
i
, with ki ≤ 3, such that
ki
[ ki
[
V (Zi ) = V (Qi, j ) , and Fi = Bi, j .
j=1 j=1
It follows by Definition 2.3 that the final collection
{(Bi, j , Qi, j )}i∈{1,...,k−1}, j∈{1,...,ki }
is a band covering with spine P for G, of size at most 3(k − 1) ≤ 288g − 141.
T HEORY OF C OMPUTING, Volume 13 (5), 2017, pp. 1–47 18
A P SEUDO -A PPROXIMATION FOR THE G ENUS OF H AMILTONIAN G RAPHS
5 Compatible pairs of planar drawings
In the previous sections, we show how to decompose the input graph to a collection of toroidal graphs. We
can use Mohar’s algorithm to find an embedding for all those toroidal graphs in linear time. Nevertheless,
the computed embeddings are not necessarily consistent. To fix this issue, we consider all pairs of bands
and corresponding toroidal embeddings and change them to make their intersections consistent. We
obtain a drawing of each pair of bands on a surface of genus O(g3 ). In the next section, we show how to
resolve the remaining slight inconsistencies to get the final embedding.
Consider two bands B1 and B2 with disjoint primary segments Q1 and Q2 , respectively. Let B =
B1 ∩ B2 (the set of edges going from Q1 to Q2 ). Denote the set of local edges incident on vertices in Q1
by L1 , and the set of edges incident on vertices in Q2 by L2 (see Figure 6.).
The main result of this section is Theorem 5.1.
Theorem 5.1. There is a polynomial-time algorithm that finds a drawing of P ∪ B ∪ L1 ∪ L2 on a surface
of genus O(g3 ).
We will use the following notion of a restriction of a drawing.
Definition 5.2 (Combinatorial restriction). Let G1 be a graph, and let G2 be a subgraph of G1 . Let ϕ1
be a drawing of G1 on some surface S1 . The combinatorial restriction of ϕ1 on G2 is defined to be
the combinatorial drawing ϕ2 of G2 induced by setting for every v ∈ V (G2 ), the ordering of the edges
incident to v in G2 to be as in ϕ1 . By gluing a disk along every facial walk in ϕ2 we obtain a surface S2 .
When this does not cause confusion, we will naturally identify f2 with the induced drawing of G2 on S2 .
Note that the genus of S2 can be smaller than the genus of S1 .
We first prove the following decomposition theorem and then show that it implies Theorem 5.1.
Theorem 5.3. There is a polynomial-time algorithm that does the following. It divides segments Q1 and
Q2 into consecutive segments Q11 , . . . , Qs1 and Q12 , . . . , Qs2 , respectively, where s = O(g). These segments
do not share any vertices except possibly for endpoints. Also it partitions all edges in B into p disjoint
sets T1 , . . . , Ts such that all edges in Ti go between Qi1 and Qi2 . For each i ∈ {1, . . . , s}, the algorithm
finds a drawing ψi of Q1 ∪ Q2 ∪ Ti ∪ L1 ∪ L2 on a surface of genus O(g2 ). Additionally, the combinatorial
restriction of ψi to Q1 ∪ Q2 ∪ L1 ∪ L2 is planar and canonical (as in Definition 2.2).
We consider canonical drawings ϕ1 and ϕ2 of B1 and B2 , respectively. Each of the drawings draws
paths Q1 and Q2 on a horizontal line ` and hence defines a total ordering of vertices in Q1 and Q2 . Let ≺1
be the ordering defined by ϕ1 and ≺2 be the ordering defined by ϕ2 . By changing the orientation of the
line ` in one of the drawings, if necessary, we may assume that ≺1 and ≺2 agree on V (Q1 ). However,
orderings ≺1 and ≺2 may define the same or opposite order on V (Q2 ). In the former case, we say that
the band intersection is regular; in the latter case, we say that the band intersection is irregular. In the
Appendix, we show that in the irregular case the intersection of bands B1 and B2 can be drawn on a
surface of genus 8. Thus Theorems 5.1 and 5.3 follow (with s = 1).
Lemma 5.4. In the irregular case, the intersection of bands B1 and B2 can be drawn on a surface of
genus 8.
T HEORY OF C OMPUTING, Volume 13 (5), 2017, pp. 1–47 19
Y URY M AKARYCHEV, A MIR NAYYERI , AND A NASTASIOS S IDIROPOULOS
Before we give the proof of the above lemma, we introduce some auxiliary results. Define two
conflict graphs C1 and C2 on the set B ∪ L1 ∪ L2 . Two nodes in C1 are connected with an edge if they are
in conflict with respect to ≺1 ; two nodes in C2 are connected with an edge if they are in conflict with
respect to ≺2 .
Lemma 5.5. Let B∗ ⊂ B be a subset of global edges such that no two edges in B∗ share an endpoint (i. e.,
B∗ is a matching). Then |B∗ | ≤ 4.
Proof. Similarly to Lemma 5.8, we have that C1 [B ∪ L1 ] and C2 [B ∪ L2 ] are bipartite graphs. So their
subgraphs C1 [B∗ ] and C2 [B∗ ] are also bipartite. However, note that two edges e1 , e2 ∈ B∗ are in conflict
with respect to ≺1 if and only if they are not in conflict with respect to ≺2 . Thus e1 and e2 are connected
with an edge in C1 [B∗ ] if and only if they are not connected with an edge in C2 [B∗ ]. Now consider
the bipartition (X,Y ) of C1 [B∗ ]. Since no two vertices in X are connected with an edge in C1 [B∗ ], X
forms a clique in C2 [B∗ ]. Since C2 [B∗ ] is a bipartite graph, |X| ≤ 2. Similarly, |Y | ≤ 2. We conclude
|B∗ | = |X| + |Y | ≤ 4.
Lemma 5.6. There exist sets of vertices X ⊂ V (Q1 ) and Y ⊂ V (Q2 ) with |X| ≤ 4, |Y | ≤ 4 such every
edge in B is incident to at least one vertex in X ∪Y .
Proof. Let B∗ be a maximal matching in B. By Lemma 5.5, |B∗ | ≤ 4. Let X be the set of endpoints of
edges in B∗ that lie in Q1 and let Y be the set of endpoints of edges in B∗ that lie in Q2 . We have |X| ≤ 4
and |Y | ≤ 4. Since B∗ is a maximal matching, every edge in B is incident to a vertex in X ∪Y .
Now we are ready to prove Lemma 5.4.
Proof of Lemma 5.4. We find sets X and Y as guaranteed by Lemma 5.6. Let B0 be the subset of edges
in B that are incident to a vertex in X; let B00 = B \ B0 . By Lemma 5.6, every edge in B00 is incident to a
vertex in Y . We consider the drawing ϕ1 restricted to Q1 ∪ L1 ∪Y ∪ B00 and the drawing ϕ2 restricted to
Q2 ∪ L2 ∪ X ∪ B0 . We assume w.l.o.g. that these two drawings do not overlap. For every point x ∈ X we
make two punctures in the plane, one in a small neighborhood of ϕ1 (x), the other in a small neighborhood
of ϕ2 (x), and attach a handle Hx between them. We perform the same operation for every y ∈ Y . Now
we define the desired drawing ψ of Q1 ∪ Q2 ∪ B ∪ L1 ∪ L2 . The drawing ψ coincides with ϕ1 on Q1 ∪ L1
and coincides with ϕ2 on Q2 ∪ L2 . We explain now how we define the drawing ψ of an edge e ∈ B00 .
Denote e = {x, y} where y ∈ Y . Let γe1 = ϕ1 (e); the curve γe1 connects ϕ1 (x) = ψ(x) and ϕ1 (y). Let γe2
be a curve drawn on the handle Hy that connects ϕ1 (y) and ϕ2 (y) = ψ(y). Then we let ψ(e) to be the
concatenation of curves γe1 and γe2 . Similarly, we define ψ(e) for edges e ∈ B0 . We obtain a drawing ψ of
Q1 ∪ Q2 ∪ B ∪ L1 ∪ L2 on a surface of genus at most 8. Edges that share a common endpoint may cross
or overlap in this drawing. We eliminate all such crossings by slightly perturbing edge drawings and
uncrossing all crossings.
In the rest of this section, we will analyze the regular case. Since in the regular case orderings ≺1 and
≺2 agree on V (Q1 ) ∪V (Q2 ), we will just denote this ordering by ≺.
Definition 5.7. Let us say that two edges {x, y}, {x0 , y0 } ∈ B ∪ L1 ∪ L2 (with x ≺ y and x0 ≺ y0 ) are in
conflict if x ≺ x0 ≺ y ≺ y0 or x0 ≺ x ≺ y0 ≺ y. We consider an auxiliary conflict graph C on the set of edges
T HEORY OF C OMPUTING, Volume 13 (5), 2017, pp. 1–47 20
A P SEUDO -A PPROXIMATION FOR THE G ENUS OF H AMILTONIAN G RAPHS
Figure 6: The figure on the left shows two bands with primary segments Q1 and Q2 , global edges
B = {1, 2, 3, 4, 5}, local edges L1 = {a, b} and L2 = {c}. The right figure shows the corresponding
conflict graph C. Note that graphs C[B ∪ L1 ] and C[B ∪ L2 ] are bipartite as claimed by Lemma 5.8.
However, the graph C is not bipartite since it contains an odd cycle 2 → 5 → c → 3 → b → 2. The graph
C[B] has three connected components S1 = {1}, S2 = {2, 4, 5} and S3 = {3} with S1 / S2 / S3 .
B ∪ L1 ∪ L2 in which e and e0 are connected with an auxiliary edge if e and e0 are in conflict. We denote
the set of connected components of C[B] (the subgraph of C induced by B) by S. (See Figure 6.)
The motivation for Definition 5.7 is that if two edges e and e0 are not conflict, we can draw them in the
plane on one side of ` or on opposite sides of `. However, if two edges are in conflict we can only draw
them on opposite sides of `. Accordingly, if the conflict graph is bipartite, then we can simultaneously
draw all the edges (the nodes of the conflict graph) in the plane. The following lemma shows that for
every S ∈ S, C[S ∪ L1 ∪ L2 ] is bipartite.
Lemma 5.8. Graphs C[B ∪ L1 ] and C[B ∪ L2 ] are bipartite. Moreover, for every S ∈ S, C[S ∪ L1 ∪ L2 ] is
bipartite.
Proof. Consider a canonical drawing of the band B1 . Let U be the set of edges in B ∪ L1 that lie above the
line ` and D be the set of edges in B ∪ L1 that lie below the line `. Note that if two edges e and e0 lie on
one side of the line `—either e, e0 ∈ U or e, e0 ∈ D—then e and e0 are not in conflict since otherwise they
would intersect. That is, e and e0 are not connected with an edge in C. Thus U ∪ D is a valid bipartition of
C[B ∪ L1 ]. We showed that C[B ∪ L1 ] is a bipartite graph. Similarly, C[B ∪ L2 ] is a bipartite graph.
Since S is connected, there is only one bipartition of S, which coincides with bipartitions of S in
C[S ∪ L1 ] and in C[S ∪ L2 ]. Thus bipartitions of C[S ∪ L1 ] and C[S ∪ L2 ] can be combined into a bipartition
of C[S ∪ L1 ∪ L2 ] (here we use that there are no edges between L1 and L2 ).
Definition 5.9. We define a partial order / on edges as follows: e / e0 for two edges e = {x, y} and
e0 = {x0 , y0 } if x x0 and y y0 (here, we assume w.l.o.g. that x ≺ y and x0 ≺ y0 ), where one of the two
inequalities is strict. We write S / S0 for two sets of edges S and S0 if e / e0 for every e ∈ S and e0 ∈ S0 .
Note that two edges e, e0 ∈ B are comparable with respect to / if and only if e and e0 are not in conflict.
Claim 5.10. The set S is totally ordered by /.
Proof. Consider two distinct connected components S, S0 ∈ S. Every two edges e ∈ S and e0 ∈ S0 are not
in conflict, and therefore either e / e0 or e0 / e. If e . e0 for all e ∈ S and e0 ∈ S0 then S . S0 and we are done.
T HEORY OF C OMPUTING, Volume 13 (5), 2017, pp. 1–47 21
Y URY M AKARYCHEV, A MIR NAYYERI , AND A NASTASIOS S IDIROPOULOS
So suppose that e / e0 for some e ∈ S and e0 ∈ S0 . Consider e00 ∈ S0 adjacent to e0 in C. We show that e / e00 .
Indeed, assume to the contrary that e / e0 and e00 / e. Then from the transitivity of partial order /, we get
that e00 / e0 , which contradicts to the fact that e0 and e00 are in conflict. Since S0 is connected in C, we
conclude that for all e00 ∈ S0 , e / e00 . Applying the same argument to S, we get that S / S0 .
We order elements of S (connected components of C[B]) with respect to to the order /: S1 / · · · / Sr .
We note that the sets S1 , . . . , Sr satisfy most properties we require in Theorem 5.3. Since sets S1 , . . . , Sr
are ordered with respect to /, endpoints of edges in sets Si divide Q1 and Q2 into r consecutive segments.
By Lemma 5.8, each graph C[S ∪ L1 ∪ L2 ] is bipartite and therefore the graph Q1 ∪ Q2 ∪ S ∪ L1 ∪ L2 is
planar. The only obstacle is that the number r of sets Si can be arbitrarily large (it is not bounded by a
function of g). To resolve this issue, we will join together some consecutive sets Si and obtain the desired
sets T j . We do that using a simple greedy algorithm. We define numbers t0 ,t1 ,t2 , . . . by induction. First,
we let t0 = 0. Let tq+1 be the largest t such that one of the following two conditions holds:
1. The graph C[Stq +1 ∪ · · · ∪ St ∪ L1 ∪ L2 ] is bipartite.
2. All edges in Stq +1 , . . . , St are in conflict with some local edge ê ∈ L1 ∪ L2 .
We stop this procedure when we process all sets Si . We obtain numbers t0 , . . . ,ts (for some s > 0). Let
Tq = Stq−1 +1 ∪ · · · ∪ Stq for every q ∈ {1, . . . , s}.
Since each set T j is the union of consecutive sets Si , we have that T1 / T2 · · · / · · · / Ts . For every p
consider all vertices in Q1 incident to edges in Tp . Let Q1p be the segment between the leftmost and
rightmost among such vertices; define Q2p similarly. Then Q11 Q21 · · · Qs1 , and Q12 Q22 · · · Qs1 .
Note that Qi1 and Q1i+1 share at most one vertex and Qi1 and Q1j are disjoint if |i − j| > 1.
Recall that we need to find a drawing of each graph Tq ∪ Q1 ∪ Q2 ∪ L1 ∪ L2 on a surface of genus
O(g2 ) and prove that s = O(g). Note that if C[Stq−1 +1 ∪ · · · ∪ Stq ∪ L1 ∪ L2 ] is bipartite (the first stopping
condition holds) then Tq ∪ Q1 ∪ Q2 ∪ L1 ∪ L2 is planar. So besides proving that s = O(g), we only need to
analyze the case when all edges in Stq−1 +1 , . . . , Stq are in conflict with some local edge ê ∈ L1 ∪ L2 . We
need the following definition that captures this case.
Definition 5.11 (Comb). Let B1 and B2 be two bands. Let B0 ⊂ B1 ∩ B2 . Suppose that all edges in B0 are
in conflict with a local edge ê ∈ L1 . Let ϕ1 and ϕ2 be canonical drawings of H1 = Q1 ∪ Q2 ∪ B0 ∪ L1 and
H2 = Q1 ∪ Q2 ∪ B0 ∪ L2 respectively (as in Definition 2.2). Note that all edges in B0 are drawn on one side
of ` in ϕ1 since all edges in B0 are in conflict with ê; we assume w.l.o.g. that all edges in B0 are drawn
above `. Then, we say that ((B1 , Q1 , ϕ1 ), (B2 , Q2 , ϕ2 ), B0 ) is a comb with spine P, or simply a comb, when
P is clear from the context.
Lemma 5.12. For every set Tp , we have
• there is a canonical planar drawing ϕ of Q1 ∪ Q2 ∪ L1 ∪ L2 ∪ Tp , or
• there are drawings ϕ1 and ϕ2 such that ((B1 , Q1 , ϕ1 ), (B2 , Q2 , ϕ2 ), Tp ) is a comb, or
• there are drawings ϕ1 and ϕ2 such that ((B2 , Q2 , ϕ2 ), (B1 , Q1 , ϕ1 ), Tp ) is a comb.
T HEORY OF C OMPUTING, Volume 13 (5), 2017, pp. 1–47 22
A P SEUDO -A PPROXIMATION FOR THE G ENUS OF H AMILTONIAN G RAPHS
Proof. Consider a set Tp . We know that either C[Tp ∪ L1 ∪ L2 ] is bipartite or all edges in Tp are in conflict
with some local edge ê ∈ L1 ∪ L2 .
First, consider the former case. Let (U, D) be the bipartition of C[Tp ∪ L1 ∪ L2 ]. There are no conflicts
between edges in U, and no conflicts between edges in D.
We arrange all vertices of Q1 ∪ Q2 on horizontal line ` according to the order ≺. We draw each edge
in U in the top half plane with respect to ` and each edge in D in the bottom half plane so that no two
edges intersect. Specifically, we consider a coordinate frame in which ` is defined by {(x, y) : y = 0}. We
draw every edge e ∈ U connecting points with coordinates (x1 , 0) and (x2 , 0) as a polygonal chain
(x1 , 0) ↔ ((x1 + x2 )/2, |x2 − x1 |/2) ↔ (x2 , 0) ;
we draw every edge e ∈ D connecting points (x1 , 0) and (x2 , 0) as
(x1 , 0) ↔ ((x1 + x2 )/2, −|x2 − x1 |/2) ↔ (x2 , 0) .
It is easy to see that no two edges intersect. We obtain the desired drawing ϕ.
Now consider the case when all edges in Tp are in conflict with some local edge ê ∈ L1 ∪ L2 . Without
loss of generality, ê ∈ L1 . Consider a canonical planar drawing ϕ1 of Q1 ∪ L1 ∪ Tp . Since every edge
e ∈ Tp is in conflict with ê, edge e lies on the other side of ` than ê. Thus all edges in Tp lie on the same
side of `. Let ϕ2 be a canonical planar drawing of Q2 ∪ L2 ∪ Tp . We get that ((B1 , Q1 , ϕ1 ), (B2 , Q2 , ϕ2 ), Tp )
is a comb.
We present an algorithm that finds a drawing of the graph H1 ∪ H2 , where H1 and H2 are as in
Definition 5.11, on a surface of genus O(g2 ) in Section 6.
It remains to show that s = O(g). First, we give a high-level overview of the proof. Roughly
speaking, we observe that Ti ∪ Ti+1 ∪ Q1 ∪ Q2 ∪ L1 ∪ L2 is not planar because if it was planar our greedy
algorithm would include Ti+1 in Ti . Then we consider s/2 graphs Ti ∪ Ti+1 ∪ Q1 ∪ Q2 ∪ L1 ∪ L2 for
i ∈ {1, 3, 5, . . . }. Each of them is not planar and there are s/2 of them. Note that the union of k
disjoint non-planar graphs has genus at least k. So we want to argue that s/2 ≤ g as otherwise the
union of graphs Ti ∪ Ti+1 ∪ Q1 ∪ Q2 ∪ L1 ∪ L2 would have genus at least s/2 > g, which would contradict
the fact that the genus of G is g. However, this approach does not work as stated because graphs
Ti ∪ Ti+1 ∪ Q1 ∪ Q2 ∪ L1 ∪ L2 share local edges. To overcome this obstacle, for each set Ti we define sets
Λi1 ⊂ L1 and Λi2 ⊂ L2 such that Ti ∪ Ti+1 ∪ Q1 ∪ Q2 ∪ Λi1 ∪ Λi2 is not planar and sets Λi1 and Λ1j do not
intersect if |i − j| > 2. This resolves the problem in the argument we outlined above (we choose indices i
with some sufficiently large constant gap). We get that s = O(g). Now we present the formal proof.
Claim 5.13. Suppose that ê ∈ L1 ∪ L2 is in conflict with edges e ∈ Sa and e0 ∈ Sb and b − a > 1. Then ê
is in conflict with edges in all sets Sc for c ∈ {a + 1, . . . , b − 1}. Moreover, each set Sc contains only one
edge.
Proof. Assume without loss of generality that ê = (x̂, ŷ) ∈ L1 where x̂ ≺ ŷ. Consider a canonical drawing
of B1 . Let e = (x, y) and e0 = (x0 , y0 ) so that x, x0 ∈ Q1 . From Sa /Sb , we get that x ≺ x0 . Since ê is in conflict
with e and e0 (and y, y0 ŷ), we have x̂ ≺ x x0 ≺ ŷ. Now if e00 = (x00 , y00 ) ∈ Sc then x̂ ≺ x x00 x0 ≺ ŷ,
and therefore e00 is in conflict with ê.
T HEORY OF C OMPUTING, Volume 13 (5), 2017, pp. 1–47 23
Y URY M AKARYCHEV, A MIR NAYYERI , AND A NASTASIOS S IDIROPOULOS
Note that if Sc contains at least two edges then it also contains two edges e1 and e2 that are adjacent
in C (since C[Sc ] is connected). Both of them are adjacent to ê in SC . So ê, e1 , and e2 form a triangle in C.
This contradicts to the fact that C[B ∪ L1 ] is bipartite.
We now show that the genus of G is at least Ω(s). Define subsets Λi1 ⊂ L1 and Λi2 ⊂ L2 such that
Ti ∪ Ti+1 ∪ Qi1 ∪ Qi2 ∪ Λi1 ∪ Λi2 are disjoint and non-planar for Ω(s) values of i. The union of these graphs
has genus at most g; on the other hand, it is at least Ω(s). Thus we conclude that s = O(g).
For a graph G and a Hamiltonian cycle C, let ≺C be an ordering of vertices induced by a traversal of C
(starting at an arbitrary vertex). We say that two edges {x1 , y1 } and {x2 , y2 } (with x1 ≺C y1 and x2 ≺C y2 )
of E(G) \ E(C) are in conflict if either x1 ≺C x2 ≺C y1 ≺C y2 or x2 ≺C x1 ≺C y2 ≺C y1 . Equivalently, this
happens when the vertices x1 , x2 , y1 , y2 are distinct and x2 and y2 are in distinct components of C \ {x1 , y1 }.
Lemma 5.14. Let G be a graph, and let C be a Hamiltonian cycle in G. The graph G is planar if and
only if there exists a partition E(G) \ E(C) = E1 ∪ E2 such that no two edges in E1 are in conflict and no
two edges in E2 are in conflict (with respect to C). In other words, G is planar if and only if and only if
the corresponding conflict graph is bipartite.
Proof. The assertion follows immediately by the Jordan Curve Theorem.
Before we define sets Λi1 and Λi2 , we define auxiliary sets L1i and L2i . Let
L1i = {e ∈ L1 : e is in conflict with some e0 ∈ Ti } ,
L2i = {e ∈ L2 : e is in conflict with some e0 ∈ Ti } .
Claim 5.15. Sets L1i and L1j are disjoint if |i − j| > 2.
Proof. Assume without loss of generality that j > i. Suppose to the contrary that there exist ê ∈ L1i ∩ L1j
then, by Claim 5.13, ê is in conflict with with all edges in Ti+1 ∪ · · · ∪ T j−1 . Thus by the construction of
sets Tp , all edges in Ti+1 ∪ · · · ∪ T j−1 must lie in one set Tp , which contradicts to the fact that j − i > 2.
Claim 5.16. Consider two edges e = (x, y) and e0 = (x0 , y0 ) in L1p ∪ L1p+1 that are connected with a path
π1 in C[L1 ]. Then they are connected with a path π2 : e = e1 → · · · → el = e0 such that the endpoints of
every er lie between the rightmost point of Q1p−10 and leftmost point of Q1p+10 . Since the graph C[L1 ] is
bipartite, the lengths of paths π1 and π2 have the same parity.
Proof. Consider a shortest path e = e1 → · · · → el = e0 in C[L1 ] between e and e0 . Denote it by π2 . Note
that ea and eb are not in conflict if |a − b| > 1 (otherwise, ea and eb would be adjacent in C[L1 ], and we
would be able to shortcut π2 ).
We claim that π2 satisfies the conditions of the lemma. Indeed, assume to the contrary that the
leftmost among endpoints of edges e1 , . . . , el lies to the left of the rightmost point of Q1p−7 (the other case
is similar). Denote this endpoint by u; let us say that u is a endpoint of et . Let v be the other end of et .
Then v lies to the left of the rightmost point of Q1p−5 . Let et−1 = (u0 , v0 ) and et+1 = (u00 , v00 ) so that u0 ≺ v0
and u00 ≺ v00 . Consider two cases.
Since et−1 and et+1 are in conflict with et (and u ≺ u0 , u ≺ v0 ), we have u0 ≺ v ≺ v0 and u00 ≺ v ≺ v00 .
Without loss of generality assume that u0 v0 and v0 ≺ v00 (note that et−1 and et+1 are not in a conflict).
T HEORY OF C OMPUTING, Volume 13 (5), 2017, pp. 1–47 24
A P SEUDO -A PPROXIMATION FOR THE G ENUS OF H AMILTONIAN G RAPHS
All edges e1 ,. . . , et−1 are not in conflict with et+1 . Thus if one of their endpoints lies between u00 and v00
then the other point also lies between u00 and v00 . Now if both endpoints of eq+1 = (xq+1 , yq+1 ) (where
q + 1 < t + 1) lie between u00 and v00 then one of the endpoints of eq lies between (xq+1 , yq+1 ) (since eq
and eq+1 conflict with each other), and thus it lies between u00 and v00 . Consequently, both endpoints of eq
lie between u00 and v00 . We conclude that all endpoints of e1 ,. . . , et−1 lie between u00 and v00 . Thus x lies
between u0 and v0 . That contradicts to the fact that u0 lies in Q1p .
Let Λi1 be the set edges in L1 whose endpoints lie between the rightmost point of Qi−11
1 and leftmost
point of Q1 . By definition, C[Ti ∪ Ti+1 ∪ L1 ∪ L2 ] is not bipartite. From Claim 5.16, we get the following
i+11
corollary.
Corollary 5.17. The graph C[Tp ∪ Tp+1 ∪ Λ1p ∪ Λ2p ] is not bipartite.
Lemma 5.18. We have s = O(genus(G)).
Proof. For every q ∈ {1, . . . , bs/40c} let fq and fq0 be two edges in T40q−38 and T40q−1 , respectively. Also,
let
Hq = Qi40q−38 ∪ · · · ∪ Q40q−1
i ∪ Q40q−38
j ∪ · · · ∪ Q40q−1
j ∪ T40q−20 ∪ T40q−21 ∪ Λ40q−20
1 ∪ Λ40q−20
2 ∪ { fq , fq0 }.
Note that graphs Hq share no edges since for all sets Q1p , Tp , Λ40q−20
1 and Λ40q−20
2 are disjoint. Moreover,
all vertices of Hq lie on the union of paths
Q40q−38
i ∪ · · · ∪ Q40q−1
i ∪ Q40q−38
j ∪ · · · ∪ Q40q−1
j .
S S
Therefore, all graphs Hq are disjoint. Since q Hq is a subgraph of G, the genus of q Hq is at most
genus(G). Thus the sum of genera of graphs Hq is at most genus(G).
Note that edges fq and fq0 and segments of paths Q1 and Q2 that lie between the endpoints of fq and
fq0 form a cycle. Endpoints of all local and global edges of Hq lie on this cycle. By Corollary 5.17, the
graph
T40q−20 ∪ T40q−21 ∪ Λ40q−20
1 ∪ Λ40q−20
2
is not bipartite, hence by Lemma 5.14, Hq is not planar.
We conclude that s = O(genus(G)).
This completes the proof of Theorem 5.3, an algorithm that finds a drawing ψi of Q1 ∪Q2 ∪Ti ∪L1 ∪L2
on a surface of genus O(g2 ) for each i. Now we are ready to prove Theorem 5.1 by combining drawings
ψi to obtain one drawing ψ.
Proof of Theorem 5.1. We assume that the drawing of ` and Q1 ∪ Q2 are the same in all drawings ψi (we
can do that without loss of generality since all vertices in Q1 ∪ Q2 are ordered with respect to ≺ in all
drawings ψi ).
First we take care of global edges in Ti . Consider the drawing ψi . Recall that if Ti is not a comb then
the drawing ψi is planar. Otherwise, it is a drawing on a plane with attached handles. In the latter case, all
handles are attached to the plane above or below either Qi1 or Qi2 . We make four punctures in the plane:
one above Qi1 (sufficiently far away from `), one below Qi1 , one above Qi2 and one below Qi2 . We attach
T HEORY OF C OMPUTING, Volume 13 (5), 2017, pp. 1–47 25
Y URY M AKARYCHEV, A MIR NAYYERI , AND A NASTASIOS S IDIROPOULOS
a handle H U between two punctures above `, and another handle H D between two punctures below `.
Now we redraw all global edges that go above ` on the handle HU , and all edges that go below ` on the
handle HD . We cut the part of the plane that lies above and below Qi1 and Qi2 . We denote this part by Ti .
The boundary of Ti consists of 4 vertical lines that pass through the left end of Qi1 , the right end of Qi1 ,
the left end of Qi2 , and the right end of Qi2 . We combine these parts Ti together and get a surface T of
genus at most O(g3 ); we do not identify boundaries of Ti except for points of ` that belong to boundaries
of several sets Ti (at this point, the surface might be disconnected). We also add line ` to T. Now we
partially define the drawing ψ on T. We draw Q1 and Q2 in ψ in the same way as they are drawn in ψi .
We draw each global edge e ∈ Ti in the same way it is drawn in ψi (on Ti ). We perform this step for all i
and obtain a drawing of all global edges.
Now we take care of local edges. Consider a local edge e whose drawing ψi partially lies in Ti . We
draw the segment of e that lies in Ti on T in the same way it is drawn on Ti . It remains to draw missing
segments of local edges and connect all segments together. We describe how we do that for edges in L1 ;
we process edges in L2 in exactly the same way.
Consider two consecutive sets Ti and Ti+1 . Let u be the the rightmost vertex of Qi1 and v be the
leftmost vertex of Qii+1 . Let ei be a global edge in Ti incident on u, and ei+1 be a global edge in Ti+1
incident on v. Let hu be the line perpendicular to u in Ti and hv be the line perpendicular to v in Ti+1 .
There are two possibilities: either u = v or u ≺ v.
First, we consider the case u = v. Let A be the set of edges e = (x, y) with x ≺ u and u ≺ y. All edges
in A are in conflict with both e and e0 . Thus all edges in A are drawn on one side of ` in ψi and ψi+1
(in particular, no two edges in A are in conflict). Consider all crossing points of edges in A and line hu
ordered descendingly by their distance from `. Since the drawing of local edges in ψi is combinatorially
planar, crossing points are ordered in the same way as corresponding edges ordered by ≺: if e1 ≺ e2 then
the crossing point of e1 is further away from ` than the crossing point of e2 . Similarly, the crossing points
of edges in A and line hv are ordered in the same way as edges in A. Thus edges cross lines hu and hv in
the same order. We attach a handle between Ti and Ti+1 and then for every edge e ∈ A draw a curve that
connects the segment of e in Ti and the segment of e in Ti+1 .
Now consider the case when u ≺ v. Let A be the set of edges e = (x, y) with x ≺ u and v ≺ y. We treat
edges in A in exactly the same way as before; we attach one handle and connect segments of edges in A
drawn on Ti and on Ti+1 . It remains to draw edges in the set
D = {e = (x, y) : x ≺ u ≺ y ≺ v or u ≺ x ≺ v ≺ y or u ≺ x ≺ y ≺ v} .
Note that A ≺ D thus all crossing points of edges in D with hu and hv lie closer to ` than crossing points
of A with hu and hv , respectively.
Denote the conflict graph C[D ∪ {ei , ei+1 }] by H.
Lemma 5.19. The graph H is bipartite.
Proof. Consider connected components of C[D]. We show that there is at most one connected component
C that is connected with both ei and ei+1 in H. Assume to the contrary that there are two such connected
components C1 and C2 . Repeating the proof of Claim 5.10, we get that if two connected components C1
and C2 of C[D] are connected with ei then either C1 /C2 or C2 /C1 . Without loss of generality, C1 /C2 .
T HEORY OF C OMPUTING, Volume 13 (5), 2017, pp. 1–47 26
A P SEUDO -A PPROXIMATION FOR THE G ENUS OF H AMILTONIAN G RAPHS
Then for every edge e = (x, y) ∈ C1 (with x ≺ y) we have x C2 and C2 y. Thus x ≺ u and v ≺ y, which
contradicts to the fact that e ∈/ A.
Let C be a connected component of C[D]. By Lemma 5.8, graphs C ∪ {ei } and C ∪ {ei+1 } are bipartite.
Since there is no edge between ei and ei+1 in H, the graph C ∪ {ei } ∪ {ei+1 } is also bipartite. We color the
graph H with two colors as follows. If there is a connected component of C[D] which is connected to both
ei and ei+1 , we first color it with 2 colors. Otherwise, we arbitrarily color nodes ei and ei+1 of H. Every
other connected component of C[D] is connected to at most one of nodes ei and ei+1 . We color it with 2
colors so that its coloring agrees with the coloring of ei and ei+1 . We obtain a valid 2-coloring of H.
Since H is bipartite there exist a canonical drawing γ of edges of D, in which all edges that are in
conflict with ei lie on one side of ` and all edges that are in conflict with ei+1 lie on one side of `. We
attach a slab Ti,i+1 above and below the segment between u and v of Q1 to T. Then we draw segments of
all edges in D on Ti,i+1 in the same way they are drawn in γ. Now the leftmost vertex of Ti,i+1 is u and
the rightmost vertex of Ti,i+1 is v. So we can use the argument we used above to connect drawings of
segments of e ∈ D drawn on Ti , Ti,i+1 , and Ti+1 .
6 Drawing a comb
In this section, we will show how to find a drawing of all the edges participating in a comb. Throughout
this section G denotes a Hamiltonian graph with a Hamiltonian path P. B1 , B2 ⊆ E(G) are two bands of
type-2, with spine P and B = B1 ∩ B2 . For i ∈ {1, 2}, Qi is the primary segment of Bi , Li is the set of its
local edges. We will assume that ((B1 , Q1 , γ1 ), (B2 , Q2 , γ2 ), B) is a comb.
6.1 Twists and minimally-twisting drawing
Definition 6.1 (Minimally-twisting drawing). Let ϕ1 = γ1 . We inductively define a canonical drawing
ϕ2 of H2 (note that there could be several such drawings, and we shall specify one of them). We
begin by drawing Q1 and Q2 on a line ` as in Definition 2.2. We then define the drawing of B. Since
((B1 , Q1 , γ1 ), (B2 , Q2 , γ2 ), B) is a comb, it follows that ≺ is a total ordering on B1 , and therefore also on B.
Let e1 , . . . , et be that ordering of B. We draw e1 above `. Given the drawing of e1 , . . . , ei−1 , we define the
drawing of ei as follows. If there exists a planar drawing of H2 that extends the current planar drawing,
and such that ei appears on the same side of ` as ei−1 , then we draw ei on the same side of ` as ei−1 .
Otherwise, we draw ei on the opposite side of `. Since B ∪ L2 is an elementary band of type-2, it follows
that one of the two drawings always exists. Finally, after defining the drawing on all edges in B, we extend
it to a canonical drawing of H2 . We say that the resulting planar drawing ϕ2 of H2 is a minimally-twisting
drawing for the comb ((B1 , Q1 , γ1 ), (B2 , Q2 , γ2 ), B). For every i ∈ {1, . . . ,t − 1}, such that ei and ei+1 are
drawn on opposite sides of ` in ϕ2 , we say that (ei , ei+1 ) is a twist.
Definition 6.2 (Short and long twists). Let G, P, B1 , B2 , B, γ1 , γ2 , L1 , L2 , H1 , H2 , ϕ1 , and ϕ2 be as in
Definition 6.1. As in Section 5, let C[B ∪ L1 ] be the conflict graph for B ∪ L1 . Let (e, e0 ) be a twist in ϕ2 .
Note that since C[B ∪ L1 ] is a bipartite graph every path P between e and e0 in C[B ∪ L1 ] is of even length.
We say that a simple path P in C[B ∪ L1 ] is a left blocking path for (e, e0 ) if all internal vertices of P
are edges in L1 and no two non-consecutive nodes of P are connected by an edge in C[B ∪ L1 ]. We say
T HEORY OF C OMPUTING, Volume 13 (5), 2017, pp. 1–47 27
Y URY M AKARYCHEV, A MIR NAYYERI , AND A NASTASIOS S IDIROPOULOS
that a left blocking path P is long if it has length at least 4 (i. e., |V (P)| ≥ 5). We say that a left blocking
path P is short if it has length 2 (i. e., |V (P)| = 3). Accordingly, we say that (e, e0 ) is a long twist if there
exists a long blocking path for (e, e0 ). We say that (e, e0 ) is a short twist if there is no such path.
Lemma 6.3. Consider a short twist (e, e0 ). Let X1 ⊂ L1 be the set of all local edges f ∈ L1 such that the
path e → f → e0 is a short blocking path for (e, e0 ). Then the edges of X1 are totally ordered by /.
Proof. Let f1 , f2 ∈ X1 . Note that f1 and f2 are in conflict with e. Since the conflict graph C[B ∪ L1 ] is
bipartite, f1 and f2 are not in conflict with each other. Let e = {a, b}, f1 = {x1 , y1 }, and f2 = {x2 , y2 }.
Assume w.l.o.g. that x1 ≺ y1 , and x2 ≺ y2 . Since each fi is a left blocking edge of (e, e0 ), it follows that
xi a yi (for i ∈ {1, 2}). Since f1 and f2 are not in conflict, we have that either x1 x2 a y2 y1
or x2 x1 a y1 y2 . Therefore, either f1 / f2 or f2 / f1 .
Definition 6.4 (Inner-most left blocking edge of a short twist). Let (e, e0 ) be a short twist. Let X1 ⊂ L1
be the set of all local edges f ∈ L1 such that the path e → f → e0 is a short blocking path for (e, e0 ). Let
f ∗ ∈ X1 be maximal with respect to /. Then we say that f ∗ is the inner-most left blocking edge of the
twist (e, e0 ). By Lemma 6.3, f ∗ is uniquely defined.
Lemma 6.5 (Right blocking paths). Let (e, e0 ) be a twist in ϕ2 . Then, there exists a path P in C[B ∪ L2 ]
between e and e0 , such that all internal vertices in P are edges in L2 , and such that |V (P)| is even. We say
that P is the right blocking path of (e, e0 ).
Proof. If there exists no right blocking path of (e, e0 ), then when computing ϕ2 , the edges e and e0 end
up on the same side of Q1 , and Q2 . Thus, since (e, e0 ) is a twist in ϕ2 , it follows that there exists a right
blocking path of (e, e0 ).
We denote the set of all long twists in ϕ2 by TL . For every long twist (e, e0 ), we choose one left long
blocking path. We denote it by P(e,e L L 0 0
0 ) . Let f be the node next to e on P(e,e0 ) and f be the node next to e
L
on P(e,e 0
0 ) . We denote the segment of Q1 between the left end of f and the right end of f by Q1,(e,e0 ) .
For every twist (e, e0 ), we find the shortest among all right blocking paths. We denote it by P(e,e R . Let
0)
R 0 0 R
f be the node next to e on P(e,e0 ) and f be the node next to e on P(e,e0 ) . We denote the segment of Q2
between the left end of f 0 and the right end of f by Q2,(e,e0 ) .
Claim 6.6. Consider a long twist (e, e0 ). Let e = {a, b} and e0 = {a0 , b0 } with a, a0 ∈ Q1 . Let f0 = 1 →
f1 → · · · → fk+1 = e0 be the left blocking path P(e,e
L
0 ) . Let f i = {xi , yi } for i ∈ {1, . . . , k} where xi ≺ yi .
Then xi+1 ≺ yi and yi xi+2 . Thus
x1 ≺ a ≺ x2 ≺ y1 x3 ≺ y2 x4 ≺ · · · ≺ xk ≺ yk−1 ≺ a0 ≺ yk .
In particular, endpoints of all edges fi lie on Q1,(e,e0 ) .
Proof. Consider two consecutive edges fi and fi+1 . First, we prove that xi+1 ≺ yi and yi ≺ xi+2 . Since fi
and fi+1 are in conflict either xi ≺ xi+1 ≺ yi or xi ≺ yi+1 ≺ yi . In the former case, xi+1 ≺ yi . In the latter
case, xi+1 ≺ yi+1 ≺ yi . We are done.
Let us now prove that yi xi+2 . Note that since no two non-consecutive nodes of P(e,e L
0 ) are connected
with an edge in the conflict graph, edges f1 , . . . , fk−1 are not in conflict with e . Therefore, yi a0 for
0
T HEORY OF C OMPUTING, Volume 13 (5), 2017, pp. 1–47 28
A P SEUDO -A PPROXIMATION FOR THE G ENUS OF H AMILTONIAN G RAPHS
i ≤ k − 1. Suppose to the contrary that xi+2 ≺ yi for some i. Consider all pairs (i, j) such that x j ≺ yi and
j ≥ i + 2. By our assumption this set is not empty. Consider pairs with the smallest value of i, and among
them choose the pair with the largest value of j. Denote this pair by (i∗ , j∗ ). Note that j∗ ≥ i∗ + 2, and
therefore, fi∗ and f j∗ are not in conflict. Thus not only x j∗ ≺ yi∗ but also y j∗ ≺ yi∗ . Since y j∗ ≺ yi∗ ≺ a0
and yk a0 , we know that j∗ < k. Using that f j∗ and f j∗ +1 are in conflict, we get that x j∗ +1 ≺ y j∗ ≺ yi∗ .
That contradicts to our choice of (i∗ , j∗ ).
Claim 6.7. Consider a twist (e, e0 ). Let e = {a, b} and e0 = {a0 , b0 } with a, a0 ∈ Q1 . Let f0 = 1 → f1 →
· · · → fk+1 = e0 be the right blocking path P(e,e
R . Let f = {x , y } for i ∈ {1, . . . , k} where x y . Then
0) i i i i i
xi+1 yi and yi xi+2 . Thus
x1 a x2 y1 x3 y2 x4 · · · xk yk−1 b yk .
In particular, endpoints of all edges fi lie on Q2,(e,e0 ) .
R
Proof. Since P(e,e R
0 ) is the shortest among all right blocking paths, no two consecutive nodes of P(e,e0 ) are
connected with an edge in the conflict graph. The proof of the claim repeats the proof of Claim 6.6.
Claim 6.8. Consider two twists (e1 , e01 ) and (e2 , e02 ). Denote the endpoints of ei by ai and bi , the
endpoints of e0i by a0i and b0i , so that bi , b0i belong to Q2 (for i ∈ {1, 2}). Suppose that e1 / e01 / e2 / e02 . Then,
V (Q2,(e1 ,e01 ) ) b02 and V (Q2,(e2 ,e02 ) ) b1 .
Proof. Let f = {x, y} be the node of P(eR 1 ,e0 ) adjacent to e01 (with x ≺ y). Note that e2 and e02 are connected
1
with P(eR 2 ,e0 ) , a path of odd length in C[B ∪ L2 ]. Since C[B ∪ L2 ] is a bipartite graph, every path between
2
e2 and e02 must have odd length. Thus f cannot be in conflict with both e2 and e02 . Moreover, since
b02 b2 b01 ≺ y, f cannot be in conflict with e02 but not with e2 . Thus f is not in conflict with e02 . Thus
x b02 and by Lemma 6.7,
V (Q2,(e1 ,e01 ) ) b02 .
Similarly,
V (Q2,(e2 ,e02 ) ) b1 .
Claim 6.9. Consider five twists {(ei , e0i )}i=1,...,5 . Denote the endpoints of ei by ai and bi , the endpoints of
e0i by a0i and b0i , so that bi , b0i belong to Q2 (for i ∈ {1, . . . , 5}). Suppose that ei / ei+1 . Then
V (Q2,(e1 ,e01 ) ) V (Q2,(e5 ,e05 ) )
and therefore we have the following properties.
1. The paths P(eR 1 ,e0 ) and P(eR 5 ,e0 ) are disjoint.
1 5
2. The paths Q2,(e1 ,e01 ) and Q2,(e5 ,e05 ) are disjoint.
T HEORY OF C OMPUTING, Volume 13 (5), 2017, pp. 1–47 29
Y URY M AKARYCHEV, A MIR NAYYERI , AND A NASTASIOS S IDIROPOULOS
Proof. From Claim 6.8, we get
V (Q2,(e1 ,e01 ) ) b02 and b3 V (Q2,(e5 ,e05 ) ) .
Note that b02 6= b2 as otherwise there would be no right blocking path between e2 and e02 . Therefore,
b02 b2 . We have,
V (Q2,(e1 ,e01 ) ) b02 b2 b3 V (Q2,(e5 ,e05 ) ) .
Parts (1) and (2) immediately follow.
Lemma 6.10 (A non-planar arrangement of five twists). Let {(ei , e0i )}5i=1 be a collection of disjoint
twists in ϕ2 . For every i ∈ {1, . . . , 5}, let P(eL i ,e0 ) and P(eR i ,e0 ) be a left and a right blocking path of (ei , e0i ),
i i
respectively. Suppose further that for any i 6= j ∈ {1, . . . , 5}, we have
V (P(eL i ,e0 ) ) ∩V (P(eL j ,e0 ) ) = 0/ , and V (P(eR i ,e0 ) ) ∩V (P(eR j ,e0 ) ) = 0/ .
i j i j
Then, the graph
5
{ei , e0i } ∪ P(eL i ,e0 ) ∪ P(eR i ,e0 )
[
Q1 ∪ Q2 ∪
i i
i=1
is non-planar.
Proof. For every i ∈ {1, . . . , 5}, let ei = {ai , bi }, e0i = {a0i , b0i }. Observe that for any {z, w} ∈ E(P(eL 3 ,e0 ) ),
3
with z ≺ w, we have
a1 a01 z ≺ w a5 a05 .
Similarly, for any {z, w} ∈ E(P(eR 3 ,e0 ) ), with z ≺ w, we have
3
b1 b01 z ≺ w b5 b05 .
Thus, J = Q1 [a1 , a05 ] ∪ Q2 [b1 , b05 ] ∪ e1 ∪ e05 ∪ e3 ∪ e03 ∪ P(eL 3 ,e0 ) ∪ P(eR 3 ,e0 ) is a graph with Hamiltonian cycle
3 3
C = Q1 [a1 , a05 ] ∪ Q2 [b1 , b05 ] ∪ e1 ∪ e05 . Since P(eL 3 ,e0 ) a left blocking path of (e3 , e03 ) it follows that in any
3
partition of the edges in E(J) \ E(C) as in Lemma 5.14, the edges e3 , and e03 have to be in the same set.
On the other hand, since P(eR 3 ,e0 ) is a right blocking path of (e3 , e03 ), it follows that e3 and e03 have to be
3
in different sets of the partition. Since this is impossible, we conclude that J is non-planar. Since J is a
subgraph of G, it follows that G is also non-planar.
Lemma 6.11. Let T be a set of twists in ϕ2 , satisfying the following conditions.
1. For every (e1 , e01 ) 6= (e2 , e02 ) ∈ T , we have {e1 , e01 } ∩ {e2 , e02 } = 0.
/
L
2. There exists a collection {P(e,e L
0 ) }(e,e0 )∈T of left blocking paths, where P(e,e0 ) is a left blocking path
for (e, e0 ) such that segments Q1,(e,e0 ) are disjoint.
Then, |T | = O(genus(G)).
T HEORY OF C OMPUTING, Volume 13 (5), 2017, pp. 1–47 30
A P SEUDO -A PPROXIMATION FOR THE G ENUS OF H AMILTONIAN G RAPHS
Proof. By Claim 6.9, we can remove at most three quarters of all twists in T so that for every two distinct
remaining twists,
V Q2,(ei ,e0i ) ∩V Q2,(e j ,e0j ) = 0/ .
Therefore, we will assume below that for i 6= j,
V Q2,(ei ,e0i ) ∩V Q2,(e j ,e0j ) = 0/
(and consequently that paths P(eR i ,e0 ) and P(eR j ,e0 ) do not intersect).
i j
Suppose that |T | ≥ 6, since otherwise the assertion is trivial (recall that we assume that G is non-
planar). For any i ∈ {0, . . . , b|T |/6c − 1}, let
5
e5i+ j ∪ e05i+ j ∪ P(eL 5i+ j ,e0
[
R
Gi = Q1,i ∪ Q2,i ∪ ) ∪ P(e5i+ j ,e0 ,
5i+ j 5i+ j )
j=1
where Q1,i (resp. Q2,i ) is the minimal subpath of Q1 (resp. Q2 ) containing all the vertices in
5
e5i+ j ∪ e05i+ j ∪ P(eL 5i+ j ,e0
[
R
5i+ j ) ∪ P(e5i+ j ,e0 5i+ j )
.
j=1
Observe that for any i 6= i0 ∈ {0, . . . , b|T |/6c − 1}, we have V (Gi ) ∩ V (Gi0 ) = 0.
/ Therefore, by
0
Lemma 6.11, for any i 6= i ∈ {0, . . . , b|T |/6c − 1}, we have V (Q1,i ) ∩ V (Q1,i0 ) = 0, / and V (Q2,i ) ∩
V (Q2,i0 ) = 0.
/
By Lemma 6.10 it follows that each graph Gi is non-planar. Since all the graphs Gi are pair-wise
vertex-disjoint subgraphs of G, it follows that genus(G) ≥ b|T |/6c, as required.
We define a partial order on the set of long twists. Let us say that
(e1 , e01 ) (e2 , e02 ) if Q1,(e1 ,e01 ) ⊂ Q2,(e2 ,e02 ) .
Then (TL , ) is a partially ordered set. We will prove now that the width of (TL , ) is O(genus(G))
and the depth of (TL , ) is O(genus(G)). Then by Dilworth’s theorem, we will conclude that |TL | =
O(genus(G)2 ).
Lemma 6.12. Let (e1 , e01 ) and (e2 , e02 ) be incomparable twists in (TL , ). Let e1 = {a1 , b1 }, e01 = {a01 , b01 },
e2 = {a2 , b2 }, and e2 = {a02 , b02 } so that a1 , a01 , a2 , a02 ∈ Q1 . Suppose that a1 ≺ a01 a2 ≺ a02 . Then
V (Q1,(e1 ,e01 ) ) a02 and a1 V (Q1,(e2 ,e02 ) ).
Proof. Let f1 be the node on PL (e1 , e01 ) adjacent to e01 . Similarly, let f2 be the node on PL (e2 , e02 ) adjacent
to e02 . Let f1 = {x1 , y1 } with x1 ≺ y1 and f2 = {x2 , y2 } with x2 ≺ y2 . Note that yi is the right end of Q1,(ei ,e0i )
for i ∈ {1, 2}. We want to prove that y1 a02 . Assume to the contrary that a02 ≺ y1 . Note that then edges
f1 and f2 are in conflict with e02 . Therefore, either f1 / f2 or f2 / f1 . Since e2 and f2 are not consecutive
nodes on P(eL 2 ,e0 ) , e2 is not in conflict with f2 . Therefore, it is impossible that f2 / f1 . Thus f1 / f2 . Then
2
y2 y1 . Now let f3 be the node on PL (e2 , e02 ) adjacent to e2 . Similarly, since f1 , f3 are in conflict with e2 ,
T HEORY OF C OMPUTING, Volume 13 (5), 2017, pp. 1–47 31
Y URY M AKARYCHEV, A MIR NAYYERI , AND A NASTASIOS S IDIROPOULOS
f1 is in conflict with e02 but f3 is not in conflict with e02 , we conclude that f1 / f3 . Therefore, Q1,(e2 ,e02 ) lies
between x1 and y1 . In particular, (e2 , e02 ) (e1 , e01 ), which contradicts to our assumption that (e1 , e01 ) and
(e2 , e02 ) are not comparable. We conclude that y1 a02 . Therefore, y1 V (Q1,(e2 ,e02 ) ).
Similarly, we prove that a1 V (Q1,(e2 ,e02 ) ).
Lemma 6.13. The width of (TL , ) is O(genus(G)).
Proof. Let (e1 , e01 ), . . . , (er , e0r ) be a maximal antichain in (TL , ). Assume that e1 /e01 /e2 /e02 /· · ·/er /e0r .
By Lemma 6.12, segments
Q1,(e1 ,e01 ) , Q1,(e3 ,e03 ) , Q1,(e5 ,e05 ) , . . .
are disjoint. Thus we can apply Lemma 6.11 to twists (e1 , e01 ), (e3 , e03 ), (e5 , e05 ), . . . . We get that r =
O(genus(G)).
Lemma 6.14. Suppose that (e1 , e01 ) (e2 , e02 ) (e3 , e03 ) and e1 / e2 . Then e1 / e3 .
Proof. Let ei = {ai , bi } and e0i = {a0i , b0i } with ai , a0i ∈ Q1 . Consider the long left blocking path P(eL 1 ,e0 )
1
for (e1 , e01 ). Let f = {x, y} be the node on the path adjacent to e01 . Suppose w.l.o.g. x ≺ y. Since
(e1 , e01 ) (e2 , e02 ) and e1 / e2 , we have that Q1,(e2 ,e02 ) lies between x and y on P. Therefore, Q1,(e2 ,e02 ) lies
to the right of a1 . Since Q1,(e3 ,e03 ) is a subset of Q1,(e2 ,e02 ) , Q1,(e3 ,e03 ) also lies to the right of a1 . Hence a3
lies to the right of a1 . We conclude that e1 / e3 .
Lemma 6.15. The depth of (TL , ) is O(genus(G)).
Proof. Let (e1 , e01 ) · · · (er , e0r ) be a maximal chain in (TL , ). Let us say (ei , e0i ) (for i < r) is of the
first type if ei / ei+1 and of the second type if ei . ei+1 . We will assume that (er , e0r ) is both of the first and
the second type.
Note that by Lemma 6.14 if ei is of the first type, then ei / e j for every j > i. Either there are at least
r/2 twists of the first type or there are at least r/2 twists of the second type. Assume w.l.o.g. that there
are at least r/2 twists of the first type. Denote them by (ẽ1 , ẽ01 ) · · · (ẽk , ẽ0k ) (where k ≥ r/2).
Now we are going to construct bk/10c disjoint non-planar subgraphs of G. By doing so, we will
prove that r = O(genus(G)). (This is similar to what we did in Lemma 6.11.)
We show how to construct the first non-planar graph G1 . Consider the left blocking paths P(eL 5 ,e0 ) and
5
P(eL 6 ,e0 ) . Let f5 and the node adjacent to e05 on P(eL 5 ,e0 ) , and f6 be the node adjacent to e06 on P(eL 6 ,e0 ) . Let h
6 5 6
be the segment of Q1 that connects the right endpoints of f3 and f5 .
The graph G1 is formed by
• edges e01 , e5 , e05 , e10 ,
• the segment of Q1 between e01 and e10 , the left blocking path P(eL 5 ,e0 ) , edges f5 , f6 and path h,
5
• the segment of Q2 between e01 and e010 , the right blocking path P(eR 5 ,e0 ) .
5
Now we replace the path formed by f5 , h and f6 with a single edge f˜5 and obtain a graph G01 . The
graph G01 has a Hamiltonian cycle formed by edges e01 and e10 and segments of paths Q1 and Q2 between
T HEORY OF C OMPUTING, Volume 13 (5), 2017, pp. 1–47 32
A P SEUDO -A PPROXIMATION FOR THE G ENUS OF H AMILTONIAN G RAPHS
these two edges. Note that P(eL 5 ,e0 ) − f5 + f˜5 is a left blocking path for (e5 , e05 ) in G01 ; also P(eL 5 ,e0 ) is a right
5 5
blocking path for (e5 , e05 ) in G01 . Thus by Lemma 5.14 the graph G01 is not planar. So G1 is not planar.
We construct graphs Gi for 2 ≤ i ≤ k/5 similarly. All graphs Gi are disjoint. Therefore, r =
O(genus(G)).
Lemma 6.16 (Bounding the number of long twists). We have |TL | = O(genus(G)2 ).
Proof. The width of (TL , ) is O(genus(G)) and the depth of (TL , ) is O(genus(G)). Thus by Dil-
worth’s theorem, |TL | = O(genus(G)2 ).
Lemma 6.17 (Bounding the number of inner-most left blocking edges). Let G, P, B1 , B2 , B, γ1 , γ2 , L1 ,
L2 , H1 , H2 , ϕ1 , and ϕ2 be as in Definition 6.1. Let TS be the set of all short twists in ϕ2 . For every twist
(e, e0 ) ∈ TS , let f(e,e0 ) be the inner-most left blocking edge of (e, e0 ). Let W = { f(e,e0 ) : (e, e0 ) ∈ TS }. Then,
|W | = O(genus(G)2 ).
Proof. For every f ∈ W , pick (e f , e0f ) ∈ TS , such that f is the inner-most left blocking edge of (e f , e0f ).
We begin by constructing a subset W 0 ⊆ W , as follows. Initially, we set W 0 = 0. / We use an auxiliary
set X, which we initialize to X = W . While X 6= 0, / we pick an edge f ∗ ∈ X, which is maximal with
respect to /. Suppose that f ∗ = {x∗ , y∗ }. We add f ∗ to W 0 , and we remove it from X. For every remaining
g 6= f ∗ ∈ X, with eg = {a, b}, e0g = {a0 , b0 }, where a, a0 ∈ V (Q1 ), we proceed as follows. If either
a x∗ a0 y∗ , (6.1)
or
x∗ a y∗ a0 , (6.2)
then we remove g from X. We repeat the above process, until X = 0. / Observe that every time we
consider some f ∈ X, we remove at most three edges from X and we add one edge to W 0 (specifically,
∗
we remove edge f ∗ , possibly one edge for which condition (6.1) holds, and possibly one edge for which
condition (6.2) holds; we add f ∗ to W 0 ). Therefore, for the resulting W 0 we have
|W 0 | ≥ d|W |/3e .
Moreover the set W 0 has the following property.
(P1) For any distinct f , g ∈ W 0 , with f = {x, y}, eg = {a, b}, e0g = {a0 , b0 }, where a, a0 ∈ V (Q1 ), we have
that at least one of the following three conditions is satisfied.
a a0 x ≺ y
x a a0 y
x ≺ y a a0
Let ψ be a drawing of G on a surface S of genus γ = genus(G). Let G0 be the graph obtained from
G by contracting Q1 to a single vertex q1 . Let ψ 0 be the drawing of G0 on a surface S0 = S/ψ(Q1 ) of
T HEORY OF C OMPUTING, Volume 13 (5), 2017, pp. 1–47 33
Y URY M AKARYCHEV, A MIR NAYYERI , AND A NASTASIOS S IDIROPOULOS
genus γ, obtained by contracting the simple curve ψ(Q1 ) to a point x. For every f ∈ W 0 , let C f = ψ 0 ( f ).
Observe that C f is a cycle in S0 , which passes through x. Consider the partition
k
W0 = Wi0 ,
[
i=1
satisfying the following conditions.
1. For any i ∈ {1, . . . , k}, for any f , g ∈ Wi0 , the cycles C f , and Cg are homotopic.
2. For any i 6= j ∈ {1, . . . , k}, for any f ∈ Wi0 , g ∈ W j0 , the cycles C f and Cg are non-homotopic.
For any i 6= j ∈ {1, . . . , k}, and for any f ∈ Wi0 , g ∈ W j0 , we have C f ∩Cg = x. By Lemma 3.4, the number
of integers i ∈ {1, . . . , k} such that the cycles C f , f ∈ Wi0 , are noncontractible is at most 6γ − 3. Moreover
there exists at most one i0 ∈ {1, . . . , k} such that the cycles C f , f ∈ Wi00 , are contractible. It follows that
k ≤ 6γ − 2 .
Thus, there exists i∗ ∈ {1, . . . , k} such that
|W 0 | |W |
|Wi0∗ | ≥ ≥ .
6γ − 2 18γ − 6
Observe that since no two edges in Wi∗ are in conflict, it follows that the directed graph on Wi∗ induced
by / is a forest. More concretely, let us consider a collection of rooted trees F = {Fi }i , such that {V (Fi )}i
is a partition of Wi∗ , and such that for any f , g ∈ Wi∗ , we have that f is a child of g in some tree Fi , if and
only if g / f , and for any h ∈ Wi∗ with h 6= g, if h / f , then h / g.
Let X ⊆ Wi0∗ be the set of all edges f ∈ Wi0∗ , such that either f is a leaf, or it has exactly one child in
the tree Fi that it belongs to. Note that
|Wi0∗ | |W |
|X| > ≥ .
2 36γ − 12
We examine all edges f ∈ X, such that f is an internal vertex in some tree Fi ∈ F. Let g be the unique
child of f . Let f = {x, y}, g = {x0 , y0 }. We have x ≺ x0 ≺ y0 ≺ y. Consider the cycle K formed by Q1 [x, x0 ],
g, Q1 [y0 , y] and f . Since C f , and Cg are homotopic, it follows that K is contractible, and therefore bounds
a disk D in S. We remove from G all edges r, such that the interior of the curve ψ(r) is contained in the
interior of D (note that we do not remove any edges from X at this step since f has only one child in the
tree). Let e f = {a, b}, e0f = {a0 , b0 }, with a, a0 ∈ V (Q1 ). By property (P1), and by the fact that f is the
inner-most left blocking edge of (e f , e0f ), it follows that either
x a a0 x0 or y0 a a0 y .
If x a a0 x0 , then we replace f with a new edge f 0 = {x, x0 }. If the edge {x, x0 } already appears in G
we add another copy of {x, x0 } (we allow multiple edges). We modify the drawing ψ so that the new edge
T HEORY OF C OMPUTING, Volume 13 (5), 2017, pp. 1–47 34
A P SEUDO -A PPROXIMATION FOR THE G ENUS OF H AMILTONIAN G RAPHS
f 0 is drawn inside the disk D. This can be done since we have deleted all edges whose image intersects
the interior of D. Notice that after doing this, the new inner-most left-blocking edge of (e f , e0f ) is f 0 .
We repeat the above process for all edges in X that are internal vertices in some tree Fi ∈ F. At the
end, we obtain a new graph G∗ , and a drawing ψ ∗ of G∗ on the same surface S of genus γ. Let
X ∗ = {(e f , e0f ) : f ∈ X} .
The set X ∗ is a collection of short twists such that the corresponding left-most blocking edges in G∗
appear consecutively on Q1 (with respect to ≺). Formally, for any (e, e0 ) ∈ X ∗ , let f(e,e 0
0 ) denote the
0 ∗ 0
inner-most left blocking edge of (e, e ) in G . Recall that, in general, f(e,e0 ) can be different than f(e,e0 ) .
Let (e, e0 ), (r, r0 ) ∈ X ∗ , and suppose that f(e,e0 ) = {x, y}, f(r,r0 ) = {z, w}, with x ≺ y, z ≺ w. Then, either
x y z w, or z w x y. Thus, ≺ induces (in the natural way) a total ordering of X ∗ . Let Y ⊆ X ∗
be the subset of X ∗ containing all odd-indexed elements in this total ordering. It follows that for any
(e, e0 ), (r, r0 ) ∈ Y , we have that the edges f(e,e
0 0
0 ) , and f (r,r 0 ) have disjoint endpoints. We apply Lemma 6.11
and get
|Y | = O(γ) .
Since |Y | ≥ |X ∗ |/2, we conclude that |W | = O(|X| · γ) = O(γ 2 ) = O(genus(G)2 ), as required.
6.2 Untwisting
In this subsection we will show how to draw a comb. We will first transform the drawing ϕ1 to a drawing
ψ1 . In drawing ψ1 all edges will be drawn in the same way as in ϕ2 . Then we will combine these two
drawings and obtain a drawing of the comb.
Rerouting left blocking edges. Let ϕ1 be a canonical drawing of Qi ∪ Li ∪ B (as in the definition of the
comb). We assume that the line ` is horizontal. We also assume that the drawing of every edge crosses
every vertical line at most once.
Let W be the set of edges f such that f is the inner-most left blocking edge for some short twist. We
perform the following transformation for every f ∈ W . We process edges from W one by one. Every time
we choose an edge that is minimal with respect to / (if there are several minimal edges, we choose any of
them).
Let f = {x, y} with x y. Consider the set of all short twists whose inner-most left blocking edge is
f . Denote it by X = {(e1 , e01 ), . . . , (er , e0r )}, where e1 / e01 / · · · / er / e0r .
Let p0x be a point on ` between ϕ1 (x) and the drawing of the next vertex to the right of x on Q1 ;
similarly let p0y be a point on ` between ϕ1 (x) and the drawing of the next vertex to the left of y on Q1 .
Consider two vertical lines h p0x and h p0y that cross ` at points p0x and p0y , respectively. Let h− −
p0x and h p0y be
subrays of h p0x and h p0y , respectively, that consist of vertices that lie below `. Let Y be the set of all local
edges g such that g / f or g = f . Note that the drawing of every edge in Y crosses h− − 0
p0x and h p0y . Let f be
the minimal edge in Y with respect to /. Each of the edges f and f 0 crosses the ray hx at one point. Let
h0x be the segment of h− 0
p0x between these crossing points. Similarly, we define hy . We puncture the plane
along segments h0x and h0y and attach a handle that connects these two punctures. Then we redraw the
segments of all edges in Y between h0x and h0y on this handle.
T HEORY OF C OMPUTING, Volume 13 (5), 2017, pp. 1–47 35
Y URY M AKARYCHEV, A MIR NAYYERI , AND A NASTASIOS S IDIROPOULOS
Then we process the next edge in W (if later we process another edge with a endpoint in x, we choose
another point p00x to the right of p0x ; similarly, if we process another edge with a endpoint in y, we choose
another point p00y to the left of p0y ).
We first reroute all left blocking edges using the procedure described above and obtain a drawing ϕ10 .
Note that all global edges are drawn in one plane in ϕ10 . We describe now how to “untwist” all twists in
this drawing and obtain a drawing compatible with ϕ2 .
x-untwisting. Let ξ be a canonical drawing of H1 on a plane with attached handles, as above. Let
x ∈ V (Q1 ). The x-untwisting of ξ is a pair (S, ξ 0 ), where S is a surface, and ξ is a drawing of H1 on S,
defined as follows. Let h be the vertical line passing through ξ (x). Suppose that the x-coordinate of ξ (x)
is χ. Let h+ , h− be the open subrays of h that are chosen as follows. The ray h+ intersects all edges in B
that intersect h above `, and it does not intersect any other edges. Similarly, h− intersects all edges in B
that intersect h below `, and it does not intersect any other edges (see Figure 7(a)).
If the line h does not cross any local edges then rays h+ and h− start at point x (but since the rays are
open, point x does not belong to them). In this case, we say that the untwisting is trivial. Otherwise, we
say that the untwisting is non-trivial.
Let S0 be the surface obtained by cutting R2 along h+ , and along h− . Formally, let S0 be the
topological closure of R2 \ (h+ ∪ h− ) (see Figure 7(b)). Intuitively, S0 is obtained by cutting the plane
along h, and by connecting the two resulting surfaces on the point where h meets `. Cutting R2 along
the ray h+ gives rise to a surface with a boundary consisting of two copies of h+ , which we denote
by left(h+ ), and right(h+ ) respectively. Similarly, cutting along h− gives rise to two boundary rays
left(h− ), and right(h− ) respectively. Moreover, every point p ∈ h+ , naturally corresponds to two points
left(p) ∈ left(h+ ), right(p) ∈ right(h+ ). Similarly, every point p ∈ h− , corresponds to two points
left(p) ∈ left(h− ), right(p) ∈ right(h− ).
Let X be the set of edges e ∈ B, such that the interior of the curve ξ (e) intersects h. Note that X is a
prefix of B with respect to ≺. Consider the partition X = X + ∪ X − , where
X + = {e ∈ X : ξ (e) ∩ h+ 6= 0}
/ , and X − = {e ∈ X : ξ (e) ∩ h− 6= 0}
/ .
For every e ∈ X, let p(e) be the point where ξ (e) intersects h. Notice that after cutting the plane along
two rays, the drawing ξ does not correspond to a valid graph drawing on S0 . This is because the edges
with images that cross the two deleted rays, are now drawn only partially. Let X + = {b+ +
1 , . . . , br }, where
the edges are ordered with respect to the y-coordinates of the corresponding intersection points p(b+ i ),
i ∈ {1, . . . , r}. Similarly, let X − = {b− 1 , . . . , b − }, where again the points are ordered with respect to
s
the y-coordinate of the intersection points p(b− i ), i ∈ {1, . . . , s}. For every e ∈ X, we flip around ` the
part of the image of ξ (e) that lies to the right of h (see Figure 7(c)). Notice that since X is a prefix of
B (with respect to ≺), this can be done without introducing any crossings. For a point p ∈ h, let −p
denote the point in h obtained by negating the y-coordinate of p. Let A1 be the segment in left(h+ )
between left(p(b+ + −
1 )), and left(p(br )), and let A2 be the segment in right(h ) between right(−p(b1 )),
+
−
and right(−p(br )). Similarly, let A3 be the segment in left(h ) between left(p(b1 )), and left(p(b−
+ −
s )),
+ − −
and let A4 be the segment in right(h ) between right(−p(b1 )), and right(−p(bs )). We add a Möbius
band M1 connecting A1 with A2 , and a Möbius band M2 connecting A3 with A4 . We can now connect the
T HEORY OF C OMPUTING, Volume 13 (5), 2017, pp. 1–47 36
A P SEUDO -A PPROXIMATION FOR THE G ENUS OF H AMILTONIAN G RAPHS
(a) A canonical drawing of H1 , and the rays h+ , and h− . (b) Cutting R2 along the rays h+ , and h− .
(c) Flipping around ` the right parts of the edges that cross (d) Adding the Möbius bands M1 , and M2 , and completing
the rays. the drawing of the edges in X along them.
Figure 7: An example of a x-untwisting.
partial drawings of the edges in X + , by drawing them in M1 . Similarly, we can draw the edges in X − in
M2 (see Figure 7(d)). Let S be the resulting surface, and ξ 0 the resulting drawing of H1 on S.
{x1 , . . . , xt }-multi-untwisting. Let ξ be a canonical drawing of H1 on a plane with attached handles
(as above), and let x1 , . . . , xt ∈ V (Q1 ) be distinct vertices. Then, the {x1 , . . . , xt }-multi-untwisting of ξ
is a pair (S, ξ 0 ), where S is a surface, and ξ 0 is a drawing of H1 on S, defined as follows. Suppose that
after reordering of the indices, we have x1 ≺ x2 ≺ · · · ≺ xt . Then, intuitively, the drawing ξ 0 is obtained
starting from ξ , and inductively taking an xi -untwisting of the current drawing, for i = 1, . . . ,t. Note that
after taking the x1 -untwisting of ξ , the graph is not necessarily drawn on a plane with attached handles,
so the precise definition is a bit more subtle. For any i ∈ {1, . . . ,t}, let `t be the vertical line that intersects
` at ξ (xi ). We inductively define a sequence {(Si , ξi0 )}ti=0 , where Si is a surface, and xi0 is a drawing of H1
T HEORY OF C OMPUTING, Volume 13 (5), 2017, pp. 1–47 37
Y URY M AKARYCHEV, A MIR NAYYERI , AND A NASTASIOS S IDIROPOULOS
on Si , with S0 be the surface on which the drawing ξ is drawn, and ξ00 = ξ . For i > 0, (Si , ξi0 ) is defined
−
as follows. We cut Si−1 along `+ i , and `i , as in the untwisting paragraph, we flip along ` the parts of the
images of the global edges crossing `, to the right of `i , we add the two Möbius bands M1 , and M2 , and
we draw the crossing edges along these two bands. The details are exactly the same as in the untwisting
paragraph, and they are therefore omitted. After performing the above operations for all i = 1, . . . ,t, we
obtain St , and ξt . We set S = St , and ξ 0 = ξt .
Lemma 6.18. Let ϕ10 be a drawing of H1 on a surface S, which is a plane with several attached handles
(as above). Let X ⊆ V (Q1 ), and let (S0 , ξ 0 ) be the X-multi-untwisting of ξ . Let r be the number of
non-trivial untwistings in X. Then, the surface S0 has genus genus(S) + O(r).
Proof. Note that when we do a trivial untwisting, we do not change the genus of a surface. Each
time we do a non-trivial untwisting, we create 2 punctures, and then add 2 Möbius bands between
boundary segments. Since adding one such Möbius band increases the genus by at most one, the assertion
follows.
Lemma 6.19. Let (e, e0 ) be a short twist. Let e = {x, y} and e0 = {x0 , y0 } with x, x0 ∈ V (Q1 ) and x x0 .
Then there is a vertex w on Q1 that lies between x and x0 , such that ϕ10 (w)-untwisting of ϕ10 is trivial.
Proof. Denote the inner-most left blocking edge of (e, e0 ) by f . Let f = {a, b} with a ≺ b. Consider the
set of edges Y = {g : f / g}.
For every point p ∈ `, let h p be the vertical line passing through p. Note that for every point p ∈ `
between ϕ10 (x) and ϕ10 (y), if the line h p crosses a local edge g in ϕ10 then f / g since we routed f and all
edges g with g / f on handles in ϕ10 .
Consider the conflict graph C[Y ∪ {e, e0 }]. Note that e and e0 are not connected in C[Y ∪ {e, e0 }] by
a path of length 2 since f is the inner-most left blocking edge for (e, e0 ); e and e0 are not connected in
C[Y ∪ {e, e0 }] by a path of length more than two since (e, e0 ) is a short twist. Therefore, e and e0 are
disconnected in C[Y ∪ {e, e0 }]. Denote the connected component of C[Y ∪ {e, e0 }] that e belongs to by C.
Let w be the rightmost of endpoints of edges in C. We have, x w y. Note that if the drawing ϕ10 (g) of
an edge g ∈ Y crosses hϕ10 (w) , then g must belong to C and at the same time the right endpoint of g must
lie to the right of w, which is impossible. We conclude that hϕ10 (w) does not cross any edges in Y , and,
therefore, any local edges in ϕ10 . Thus ϕ10 (w)-untwisting of ϕ10 is trivial.
Lemma 6.20 (Drawing a comb). Let G, P, B1 , B2 , B, L1 , L2 , H1 , H2 , ϕ1 , and ϕ2 be as in Definition 6.1.
Then, there exists a polynomial-time algorithm that computes a drawing of H1 ∪ H2 on a surface of
genus O(genus(G)2 ). The combinatorial restriction of this drawing to Q1 ∪ Q2 ∪ L1 ∪ L2 is planar and
canonical.
Proof. We first reroute left blocking edges as described above. By Lemma 6.17, we get a drawing ϕ10 of
H1 on a surface of genus O(genus(G)2 ).
Now we construct a set X so that X-multi-untwisting untwists all twists. We do the following for
every twist (e, e0 ). Let e = {x, y} and e0 = {x0 , y0 } with x, x0 ∈ V (Q1 ) and x x0 . If the twist (e, e0 ) is a
long twist, we choose an arbitrary point p on ` between ϕ10 (x) and ϕ10 (x0 ) and add it to X. If the twist
{e, e0 } is a short twist, we find a vertex w such that ϕ10 (w)-untwisting is trivial, using Lemma 6.19. Then
we add ϕ10 (w) to X.
T HEORY OF C OMPUTING, Volume 13 (5), 2017, pp. 1–47 38
A P SEUDO -A PPROXIMATION FOR THE G ENUS OF H AMILTONIAN G RAPHS
Now we perform X-multi-untwisting. The number of non-trivial untwistings equals the number of
long twists, and by Lemma 6.16, it is O(genus(G)2 ). Thus by Lemma 6.18, we obtain a drawing ψ1 of
the comb on a surface of genus at most O(genus(G)2 ).
The drawing ψ1 is consistent with ϕ2 in the following sense: every global edge goes above Q2 in ψ1
if and only if it goes above Q2 in ϕ2 . Thus we can combine drawings ψ1 and ϕ2 . We obtain a drawing of
the comb on a surface of genus O(genus(G)2 ).
7 Drawing a Hamiltonian graph
In previous sections, we showed how to obtain O(g2 ) embeddings that are almost consistent. In this
section, we show how to resolve all remaining inconsistencies to obtain the final embedding.
Definition 7.1 (Internal and marginal edges). Let G be a graph, and let S ⊆ V (G). An edge {u, v} ∈ E(G)
is called S-marginal if and only if exactly one of u and v is in S; it is called S-internal if and only if both
u and v are in S.
Definition 7.2 (Extended graph). Let G be a graph, and let S ⊆ V (G). Let M ⊆ E(G) be the set of all
S-marginal edges. We denote by G[S] the subgraph of G induced by S. Let J be the graph obtained
starting from G[S], and adding for every e = {u, v} ∈ M, with v ∈ S, a new vertex ue , and the edge {ue , v}.
We refer to e0 as the copy of e in J. Formally, we define J to be the graph with
[ [
V (J) = S ∪ {ue } , and E(J) = E(G[S]) ∪ {ue , v} .
e∈M e={u,v}∈M,v∈S
With this notation, the edge {ue , v} is the copy of e in H. We refer to J as the S-extended graph (with
respect to G).
Definition 7.3 (Extended drawing). Let G be a graph, let H be a subgraph of G, let S ⊆ V (H), and let ϕ
be some drawing of H. Let ϕ 0 be a drawing obtained from ϕ by embedding each V (H)-marginal edge
in a face that contains one of its endpoints (recall that each marginal edge is attached to a leaf). Let ϕ 00
be the drawing obtained by ϕ 0 by removing the vertices in V (H)\S. We say ϕ 00 is a S-extended drawing
induced from ϕ.
Definition 7.4 (Agreement). Let G be a graph, and let S1 , S2 ⊆ V (G). For any i ∈ {1, 2}, let ψi be an
Si -extended drawing. We say that ψ1 and ψ2 agree on a vertex v ∈ S1 ∩ S2 if and only if the cyclic
orderings assigned to edges incident to v in ψ1 and ψ2 become identical after identifying each edge in the
extended graph with its copy in G. We say that ψ1 and ψ2 agree if they agree on all vertices in S1 ∩ S2 .
Definition 7.5 (Interval of marginal edges). Let G be a graph, and let P be a Hamiltonian path in G. Let
S ⊆ V (G), let M be the set of S-marginal edges, and let ψ be an S-extended drawing. Let M 0 ⊆ M, and
let P0 be a subpath of P. We say that (M 0 , P0 ) is an (ψ, P)-interval of S-marginal edges if and only if the
following conditions are satisfied:
1. All edges in M 0 are incident to P0 .
2. All edges in M 0 appear on the same side of P in ψ.
T HEORY OF C OMPUTING, Volume 13 (5), 2017, pp. 1–47 39
Y URY M AKARYCHEV, A MIR NAYYERI , AND A NASTASIOS S IDIROPOULOS
3. All edges in M 0 are drawn inside a single face of ψ.
4. Let e ∈ M \ M 0 . Then, either e is not incident to P0 , or it is incident to one of the endpoints of P0 , or
it appears on the opposite side of P than the edges in M 0 in the drawing ψ.
5. Let F be the face in ψ that contains all edges in M 0 , and let ≺ be the total ordering of the edges
incident to P0 , induced by a traversal of F. Then, all edges in M 0 form a contiguous interval of ≺.
The path P0 is called the subpath of the interval (M 0 , P0 ). Two intervals are called disjoint if their subpaths
are vertex disjoint.
Definition 7.6 (Essential Drawing of a sub-band). Let G be a graph of genus g, and let P be a Hamiltonian
path in G. For 1 ≤ i ≤ 2, let (Bi , Qi ) be a band, Li be its local edges. Let B = B1 ∩ B2 , H = Q1 ∪ Q2 ∪ B ∪
L1 ∪ L2 and ϕ be an embedding of H. For 1 ≤ i ≤ 2 we make the following definitions.
1. Ea [i] and Eb [i] to be the subset of edges of B that are incident to Qi from above and below,
respectively.
2. xa [i] and ya [i] to be the first and last vertex incident to Ea [i], with respect to ≺ on Qi ; similarly, xb [i]
and yb [i] are the first and last vertex incident to Eb [i].
3. Qa [i] to be the minimal subpath of Qi that contains xa [i] and ya [i], and Qb [i] to be the minimal
subpath of Qi that contains xb [i] and yb [i].
4. VR [i] = V (Qa [i]) ∪V (Qb [i]), note that VR [i] is composed of the vertices of at most 2 subpaths of Qi .
5. VR = VR [1] ∪VR [2].
6. The B-essential drawing induced from ϕ, to be the VR -extended drawing induced from ϕ.
Lemma 7.7 (Path splitting). Let G be a graph of genus g and α1 , α2 and γ be three mutual vertex disjoint
paths in G such that each edge in E(G)\E(γ) that is incident to γ is also incident to α1 ∪ α2 . Let H be a
graph satisfying the following conditions.
1. H contains two copies of V (γ), V1 and V2 , and one copy of all vertices in V (G)\V (γ). For any
vertex x ∈ V (γ) we write x[i] to denote the copy of x in Vi , 1 ≤ i ≤ 2.
2. For any {u, v} ∈ E(G) if u, v ∈ V (γ) then {u[1], v[1]}, {u[2], v[2]} ∈ E(H).
3. For any {u, v} ∈ E(G) if u, v 6∈ V (γ) then {u, v} ∈ E(H).
4. For any {u, v} ∈ E(G) and 1 ≤ i ≤ 2 if u ∈ V (αi ) and v ∈ V (γ) then {u, v[i]} ∈ E(H).
Then, H has genus O(g).
Proof. Let ϕ be an embedding of G on a surface of genus g and consider the cyclic order of edges around
γ in ϕ. We say two edges are homotopic if and only of they are homotopic after contracting α1 , α2 and
γ. For each edge e incident to γ we say that e has type one if it is incident to α1 and has type two if it
is incident to α2 . Observe that the set of type one edges (and similarly the set of type two edges) fall
T HEORY OF C OMPUTING, Volume 13 (5), 2017, pp. 1–47 40
A P SEUDO -A PPROXIMATION FOR THE G ENUS OF H AMILTONIAN G RAPHS
into O(g) homotopy classes. Since two homotopic edges, αi (i ∈ {1, 2}) and γ form the boundary of a
topological disc, different homotopy classes cannot interleave. It follows that in the cyclic order of edges
around γ, switching between type one and type two edges happen O(g) times.
Now, to build an embedding of H of genus O(g), we add γ 0 , a copy of γ, and for each maximal
consecutive set of type one edges we disconnect them from γ and add one handle to reroute them and
connect them to γ 0 .
Lemma 7.8. Let G be a graph of genus g, and let P be a Hamiltonian path in G. Let B1 , B2 ⊆ E(G) be
bands with spine P, and with primary segments Q1 , and Q2 , respectively. Assume that B = B1 ∩ B2 . Let
H = Q1 ∪ Q2 ∪ L1 ∪ L2 ∪ B. Then, there is an embedding ϕ of H on a surface of genus O(g3 ) such that
the B-essential drawing induced from ϕ has all its V (H)-marginal edges on a collection of at most O(g3 )
disjoint intervals.
Proof. Let M be the set of V (H)-marginal edges. Let Mout be the set of vertices such that each v ∈ Mout
is an endpoint of at least one marginal edge and v 6∈ Q1 ∪ Q2 . Mout can be decomposed into at most 3
disjoint segments, γ1 , γ2 and γ3 , of P that are disjoint from Q1 and Q2 .
Let H 0 be the graph obtained by adding the edges M to H. We use Lemma 7.7 to obtain the genus
O(g) graph H 00 by splitting γ1 , γ2 and γ3 . We obtain paths γi0 and γi00 , for 1 ≤ i ≤ 3, so that there is no edge
between γi0 and Q2 and there is no edge between γi00 and Q1 . It follows that we can extend Q1 and Q2 and
treat marginal edges as local edges in H 00 .
Now we use Lemma 5.1 to obtain a drawing of H 00 on a surface of genus O(g3 ). Since the marginal
edges form a cut between Q1 ∪ Q2 and the rest of the graph they are on at most O(g3 ) handles, and so
O(g3 ) segments.
Lemma 7.9 (Simple subband drawing). Let G be a graph of genus g, and let P be a Hamiltonian path
in G. Let B1 , B2 ⊆ E(G) be bands with spine P, and with primary segments Q1 , and Q2 , respectively.
Assume that B = B1 ∩ B2 6= 0.
/ Then, there exists S ⊆ V (G), and an S-extended drawing ψ, satisfying the
following conditions.
1. For any edge {u, v} ∈ B, both u and v are in S.
2. P[S] is composed of at most four subpaths of Q1 ∪ Q2 .
3. ψ has genus O(g3 ).
4. Let M ⊆ E(G) be the set of S-marginal edges. Then, there exists a collection of (ψ, P)-intervals
(M1 , P1 ), . . . , (Mk , Pk ), for some k = O(g3 ), such that M \ E(P) = ki=1 Mi .
S
Moreover, S and ψ can be computed in polynomial time.
Proof. We build an auxiliary graph X with genus O(g) that is composed of two bands. We find an
embedding of X, ϕX , and use it as a guide to build S and an S-extended embedding ψ.
Let P0 , Q1 , P00 , Q2 and P000 be vertex disjoint subpaths of P such that P0 Q1 P00 Q2 P000 and
V (P0 ) ∪V (Q1 ) ∪V (P00 ) ∪V (Q2 ) ∪V (P000 ) = V (P).
We build X as follows. First we make two copies of P0 , P10 and P20 , two copies of P00 , P100 and P200 , and
two copies of P000 , P1000 and P2000 . We build the path α1 by connecting P10 , Q1 , P100 and P1000 in this order and
T HEORY OF C OMPUTING, Volume 13 (5), 2017, pp. 1–47 41
Y URY M AKARYCHEV, A MIR NAYYERI , AND A NASTASIOS S IDIROPOULOS
the path α2 by connecting P20 , P200 , Q2 and P2000 in this order; here the result of connecting two paths β and
γ is the path obtained by identifying the last vertex of β with the first vertex of γ.
For each edge (u, v) ∈ G, (i) if u, v ∈ V (Q1 ) ∪V (Q2 ) then (u, v) ∈ E(X); observe that there is only
one copy of u and one copy of v in V (X), (ii) if u ∈ V (Qi ) (1 ≤ i ≤ 2) and v ∈ V (P0 ) ∪V (P00 ) ∪V (P000 )
then we connect u to the copy of v that is in V (Pi0 ) ∪V (Pi00 ) ∪V (Pi000 ) in X.
Since the genus of G is g there is an embedding ϕ ∗ of G[B1 ∪ B2 ∪ L1 ∪ L2 ∪ Q1 ∪ Q2 ] on a surface of
genus O(g). We use ϕ ∗ to build an embedding ϕX∗ of X that has genus O(g). We delete at most 4 edges
from ϕ ∗ to disconnect P0 , Q1 , P00 , Q2 and P000 . Then, we split each of P0 , P00 and P000 using Lemma 7.7.
Finally for 1 ≤ i ≤ 2 we add edges to connect Pi0 to Qi , Qi to Pi00 and Pi00 to Pi000 by adding a constant
number of handles. We also add an edge between the first vertices of P10 and P20 to ensure that X is still
Hamiltonian, which is useful when we want to apply Lemma 7.8. So the genus of X is O(g).
As X is Hamiltonian, it has genus O(g), and (B, α1 ) and (B, α2 ) are bands in X, we can use Lemma 7.8
to obtain a drawing ϕ of X on a surface of genus O(g3 ). Then we set S = VR , the essential vertex set of B,
and ψ to be the B essential drawing of ϕ. It is easy to check that S and ψ satisfy the required properties
in the lemma.
Lemma 7.10 (Subband drawing). Let G be a graph of genus g, and let P be a Hamiltonian path in G. Let
B1 , B2 ⊆ E(G) be bands with spine P, and with primary segments Q1 , and Q2 , respectively. Assume that
B = B1 ∩ B2 6= 0. / Then, there exist S1 , S2 , . . . , Sr ⊆ V (G) and for each 1 ≤ i ≤ r an Si -extended drawing
ψi , satisfying the following conditions.
1. r = O(1).
2. For any edge {u, v} ∈ B, there is an 1 ≤ i ≤ r such that both u and v are in Si .
3. For all 1 ≤ i ≤ r, P[Si ] is composed of at most four subpaths of Q1 ∪ Q2 .
4. For all 1 ≤ i ≤ r, ψi has genus O(g3 ).
5. For all 1 ≤ i ≤ r, let Mi ⊆ E(G) be the set of Si -marginal edges. Then, there exists a collection of
disjoint (ψi , P)-intervals (Mi,1 , Pi,1 ), . . . , (Mi,k , Pi,k ), for some k = O(g3 ), such that Mi = kj=1 Mi, j .
S
Moreover, Si ’s and ψi ’s can be computed in polynomial time.
Proof. For 1 ≤ i ≤ 2 the band (Bi , Qi ) has a primary segment and 3 ≤ ti ≤ 4 outlets Pi,1 , . . . , Pi,ti . For each
possible pair of α ∈ {Q1 ∩ P2,i }1≤i≤t1 and β ∈ {Q2 ∩ P1,i }1≤i≤t2 , we use the algorithm of Lemma 7.9 to
obtain a (V (α) ∪V (β ))-drawing.
There are at most 16 possible pairs of α and β to consider, so r = O(1). Property (2) holds because
we are considering every possible intersections. The other properties are implied by Lemma 7.9.
Lemma 7.11 (Decomposition). Let G be a graph of genus g, and let P be a Hamiltonian path in G. Then,
we can compute in polynomial time a collection S1 , . . . , Sk of subsets of V (G), and for every i ∈ {1, . . . , k},
an Si -extended drawing ψi , so that the following conditions are satisfied.
1. k = O(g2 ).
2. For any e ∈ E(G), there exists i ∈ {1, . . . , k} such that e is Si -internal.
T HEORY OF C OMPUTING, Volume 13 (5), 2017, pp. 1–47 42
A P SEUDO -A PPROXIMATION FOR THE G ENUS OF H AMILTONIAN G RAPHS
3. For any i ∈ {1, . . . , k}, P[Si ] has at most four connected components.
4. For any i ∈ {1, . . . , k}, ψi has genus O(g3 ), and all the Si -marginal edges are on O(g) disjoint
(ψi , P)-intervals. Moreover, for each j ∈ {1, . . . , j} the set of Si -marginal edges that are S j -internal,
are on O(g) disjoint (ψi , P)-intervals.
Proof. We compute a band covering B = {(Bi , Qi )}ti=1 of G using the algorithm of Lemma 2.5; here,
t = O(g).
Using B we build a collection that is composed of two types of vertex subsets, we call them global
and local.
To make the global subsets, for each pair 1 ≤ i, j ≤ t with Bi ∩ B j 6= 0/ we use Lemma 7.10 to obtain
an O(1) number of subsets {S1 , S2 , . . . , Sr } and their extended drawings, satisfying the properties stated
in the lemma. Note that each global edge of B is an internal edge of some Si . However, there may be
local edges that are not internal (or even marginal) edges for any Si . We build local sets to include such
local edges.
For each 1 ≤ i ≤ t, consider the planar embedding ϕi of (Bi ∪ Li ∪ (P\γi )). We color the edges of Bi
so that two edges are assigned the same color if and only if they are homotopic (when the endpoints of Qi
are treated as punctures) and they are both in B j for some j 6= i. Since there are a constant number of
homotopy classes in each band, and there are O(g) bands, it follows that the required number of colors is
O(g).
In ϕi and on each side of Qi we define a set of segments, each to be the minimal subpath of Qi that
is incident to all edges of a certain color on that side of Qi ; a segment inherits the color of its incident
global edges. By the definition of homotopy the segments on each side are edge disjoint. Observe that
there may be vertices on Qi that are not assigned any color on one or both sides. To cover each side of Qi
we introduce O(g) segments of void color on each side to cover the gaps between already colored. We
say that a subpath of Qi is colorful on a certain side if and only if it does not intersect any segment of
void color on that side.
To compute the local subsets we remove all maximal subpaths of Qi that are colorful on both sides to
obtain O(g) candidate subpaths. We say that two candidate subpaths are connected if and only if there
is an edge on E(G) \ E(P) with one endpoint incident to each of them. Planarity of ϕ implies that each
candidate subpath is connected to at most one other candidate subpath.
We start with the vertex set of O(g) candidate subpaths and merge two such sets if their corresponding
subpaths are connected. So, we acquire a collection of O(g) subsets each composed of at most 2 subpaths
of Qi . By construction the genus of any local set is zero and all its marginal edges are on O(g) disjoint
intervals. The union of all global and local sets together with the embeddings is a collection of vertices
and extended embeddings satisfying all of the required properties.
Lemma 7.12 (Conflict resolution). Let G be a graph, and let P be a Hamiltonian path of G. Let
S1 , S2 ⊆ V (G), and Mi , Ii and ψi be the set of marginal edges, the set of internal edges and Si -extended
embeddings, 1 ≤ i ≤ 2, all satisfying the following properties.
1. P[Si ] is composed of at most four subpaths of P.
2. ψi has genus ≤ γ and all marginal edges Mi are on ≤ α disjoint (ψi , P)-intervals.
T HEORY OF C OMPUTING, Volume 13 (5), 2017, pp. 1–47 43
Y URY M AKARYCHEV, A MIR NAYYERI , AND A NASTASIOS S IDIROPOULOS
3. In ψ1 the marginal edges M1 ∩ I2 can be covered by ≤ α disjoint (ψ1 , P)-intervals. Similarly, in
ψ2 the marginal edges M2 ∩ I1 can be covered by ≤ α disjoint (ψ2 , P)-intervals.
Then, in polynomial time the extended embedding ψ10 of genus O(γ + α) that agrees with ψ2 can be
computed. Further, all edges in M1 ∩ I2 can be covered by ≤ 2α disjoint intervals in ψ10
Proof. Let A = {a1 , a2 , · · · , a p } be the set of intervals of ψ1 that covers M1 ∩ I2 and B = {b1 , b2 , · · · , bq }
be the set of intervals of ψ2 that covers M2 ∩ I1 . Then, we consider, Π = {π1 , π2 , . . . , πr }, the set of the
mutual intersection of a ∈ A and b ∈ B. Both A and B are composed of intervals and by assumption p ≤ α
and q ≤ α. It follows that r ≤ 2α.
Observe that πi ’s are the only possible subpaths of P on which the embeddings ψ1 [I1 ∪ I2 ] and
ψ2 [I1 ∪ I2 ] may not agree. Further, on each πi edges in M1 and M2 are on two different sides in both ψ1
and ψ2 .
Now we build a new extended embedding ψ10 of S1 that agrees with ψ2 . We start with ψ1 and a copy
ψ of ψ2 [S1 ∩ S2 ] and modify ψ1 by rerouting all the edges in I1 ∩ M2 to go to ψ 0 and deleting ψ1 [S1 ∩ S2 ]
0
at the end of the day. By assumption ψ1 and ψ 0 both have genus at most γ, we use ≤ 2α + 4 handles or
Möbius bands for rerouting the edges, so ψ10 will have genus ≤ 2γ + 2α + 8.
We first reroute the edges of I1 ∩ M2 that are in P. Since, each of P[S1 ] and P[S2 ] are composed of
at most 3 subpaths, P[S1 ∩ S2 ] is composed of at most 6 subpaths. Therefore the edges of P that are in
I1 ∩ M2 can be rerouted by adding at most 12 handles.
We reroute the edges of I1 ∩ M2 that are not in P by considering πi ’s in turn. For a fixed πi we know
that all the edges in I1 ∩ M2 are connected to πi from a single side in both ψ1 and ψ2 (and so ψ 0 ). So we
can reroute that set of edges by using a handle or a Möbius band. Thus, we need at most 2α handles or
Möbius bands to reroute all such edges.
Since no subpath of Π is incident to any marginal edge of M1 \I2 , all other marginal edges are still on
α disjoint intervals after the above surgery in ψ10 .
It follows from the construction that all marginal edges M1 ∩ I2 are on 2α intervals of ψ10 .
Theorem 7.13 (Main result). There exists a polynomial-time algorithm which given a graph G of
orientable genus g, and a Hamiltonian path in G, outputs a drawing of G on a surface of either orientable,
or non-orientable genus O(g7 ).
Proof. First we use Lemma 7.11 to compute {S1 , S2 , . . . , Sk } and {ψ1 , ψ2 , . . . , ψk } satisfying the condi-
tions of Lemma 7.11.
Then, for each pair of Si and S j we resolve the conflict using Lemma 7.12. Let the extended embedding
we obtain for each Si at the end of all conflict resolutions be ψi0 .
The genus of the extended embedding of each Si increases by O(g) after each conflict resolution and
k = O(g2 ), so the genus of each ψi0 is O(g3 ). Further, for all 1 ≤ i, j ≤ k the set of edges Mi ∩ I j are on
O(g3 ) disjoint intervals of ψi0 . It follows that Mi are on O(g5 ) disjoint intervals of ψi0 .
Since {ψ10 , ψ20 , . . . , ψk0 } mutually agree, they collectively describe an embedding of G. On the other
hand, each ψi0 has genus O(g3 ) and can be disconnected from the rest of G by cutting along O(g5 ) handles
or Möbius bands. It follows that the genus of the entire embedding is O(kg5 ) = O(g7 ).
T HEORY OF C OMPUTING, Volume 13 (5), 2017, pp. 1–47 44
A P SEUDO -A PPROXIMATION FOR THE G ENUS OF H AMILTONIAN G RAPHS
References
[1] C HANDRA C HEKURI AND A NASTASIOS S IDIROPOULOS: Approximation algorithms for Euler
genus and related problems. In Proc. 54th FOCS, pp. 167–176. IEEE Comp. Soc. Press, 2013.
[doi:10.1109/FOCS.2013.26, arXiv:1304.2416] 2, 3
[2] J IANER C HEN , S AROJA P. K ANCHI , AND A RKADY K ANEVSKY: A note on approximating graph
genus. Inform. Process. Lett., 61(6):317–322, 1997. [doi:10.1016/S0020-0190(97)00203-2] 2
[3] I ON S. F ILOTTI , G ARY L. M ILLER , AND J OHN H. R EIF: On determining the genus of a graph in
O(vO(g) ) steps. In Proc. 11th STOC, pp. 27–37. ACM Press, 1979. [doi:10.1145/800135.804395] 2
[4] J ONATHAN L. G ROSS AND T HOMAS W. T UCKER: Topological Graph Theory. Courier Corporation,
1987. 2
[5] A LLEN H ATCHER: Algebraic Topology. Cambridge Univ. Press, 2002. Available at the author’s
webpage. 2
[6] J OHN E. H OPCROFT AND ROBERT E NDRE TARJAN: Efficient planarity testing. J. ACM, 21(4):549–
568, 1974. [doi:10.1145/321850.321852] 2
[7] K EN - ICHI K AWARABAYASHI , B OJAN M OHAR , AND B RUCE A. R EED: A simpler linear time algo-
rithm for embedding graphs into an arbitrary surface and the genus of graphs of bounded tree-width.
In Proc. 49th FOCS, pp. 771–780. IEEE Comp. Soc. Press, 2008. [doi:10.1109/FOCS.2008.53] 2
[8] K EN - ICHI K AWARABAYASHI AND A NASTASIOS S IDIROPOULOS: Beyond the Euler characteristic:
Approximating the genus of general graphs. In Proc. 47th STOC, pp. 675–682. ACM Press, 2015.
[doi:10.1145/2746539.2746583, arXiv:1412.1792] 2, 3
[9] Y URY M AKARYCHEV, A MIR NAYYERI , AND A NASTASIOS S IDIROPOULOS: A pseudo-
approximation for the genus of Hamiltonian graphs. In Approximation, Randomization, and Combi-
natorial Optimization. Algorithms and Techniques, pp. 244–259. Springer, 2013. [doi:10.1007/978-
3-642-40328-6_18] 1
[10] A LEKSANDER M ALNI Č AND B OJAN M OHAR: Generating locally cyclic triangulations of surfaces.
J. Combin. Theory Ser. B, 56(2):147–164, 1992. [doi:10.1016/0095-8956(92)90015-P] 9
[11] B OJAN M OHAR: A linear time algorithm for embedding graphs in an arbitrary sur-
face. SIAM J. Discrete Math., 12(1):6–26, 1999. Preliminary version in STOC’96.
[doi:10.1137/S089548019529248X] 2
[12] B OJAN M OHAR: Face covers and the genus problem for apex graphs. J. Combin. Theory Ser. B,
82(1):102–117, 2001. [doi:10.1006/jctb.2000.2026] 2
[13] B OJAN M OHAR AND C ARSTEN T HOMASSEN: Graphs on Surfaces. John Hopkins Univ. Press,
2001. 2
T HEORY OF C OMPUTING, Volume 13 (5), 2017, pp. 1–47 45
Y URY M AKARYCHEV, A MIR NAYYERI , AND A NASTASIOS S IDIROPOULOS
[14] N EIL ROBERTSON AND PAUL D. S EYMOUR: Graph minors. VIII. A Kuratowski theorem for gen-
eral surfaces. J. Combin. Theory Ser. B, 48(2):255–288, 1990. [doi:10.1016/0095-8956(90)90121-F]
2
[15] C ARSTEN T HOMASSEN: The graph genus problem is NP-complete. J. Algorithms, 10(4):568–576,
1989. [doi:10.1016/0196-6774(89)90006-0] 2
[16] C ARSTEN T HOMASSEN: Triangulating a surface with a prescribed graph. J. Combin. Theory Ser. B,
57(2):196–206, 1993. [doi:10.1006/jctb.1993.1016] 2
[17] A RTHUR T. W HITE: Graphs of Groups on Surfaces: Interactions and Models. Volume 188.
Elsevier, 2001. 2
AUTHORS
Yury Makarychev
Associate professor
Toyota Technological Institute – Chicago
yury ttic edu
http://ttic.uchicago.edu/~yury/
Amir Nayyeri
Assistant professor
Oregon State University
Corvallis, OR
nayyeria eecs oregonstate edu
http://web.engr.oregonstate.edu/~nayyeria/
Anastasios Sidiropoulos
Assistant professor
The Ohio State University
sidiropoulos.1 osu edu
http://sidiropoulos.org
T HEORY OF C OMPUTING, Volume 13 (5), 2017, pp. 1–47 46
A P SEUDO -A PPROXIMATION FOR THE G ENUS OF H AMILTONIAN G RAPHS
ABOUT THE AUTHORS
Y URY M AKARYCHEV is an associate professor of computer science at TTIC. He received
an MS in Mathematics in 2001 from Moscow State University and a Ph. D. in Computer
Science in 2008 from Princeton University, advised by Moses Charikar. Yury served
as a postdoctoral researcher at Microsoft Research in Redmond, WA, and Cambridge,
MA. Upon completion of the postdoc at Microsoft, Yury joined TTIC in 2009. Yury’s
research interests include combinatorial optimization, approximation algorithms, and
metric geometry.
A MIR NAYYERI received his Ph. D. in computer science in 2012 from the University of
Illinois at Urbana-Champaign, advised by Jeff Erickson. He is currently an assistant
professor at Oregon State University. His research interest is in algorithm design,
particularly for problems in geometry and topology.
A NASTASIOS S IDIROPOULOS, called “Tasos” by his friends and colleagues, is an assistant
professor at the Computer Science & Engineering and the Mathematics Departments
at The Ohio State University. He received his Ph. D. from the Massachusetts Institute
of Technology in 2008, advised by Piotr Indyk. His research focuses on developing
algorithms for the analysis of graphs and geometric data sets.
T HEORY OF C OMPUTING, Volume 13 (5), 2017, pp. 1–47 47