See discussions, stats, and author profiles for this publication at: https://www.researchgate.

net/publication/220616693

Hamilton Paths in Grid Graphs

Article in SIAM Journal on Computing · November 1982

DOI: 10.1137/0211056 · Source: DBLP

CITATIONS READS
564 8,780

3 authors, including:

Alon Itai Jayme Luiz Szwarcfiter

Technion – Israel Institute of Technology Federal University of Rio de Janeiro
120 PUBLICATIONS 8,613 CITATIONS 335 PUBLICATIONS 3,997 CITATIONS

SEE PROFILE SEE PROFILE

All content following this page was uploaded by Jayme Luiz Szwarcfiter on 03 February 2015.

The user has requested enhancement of the downloaded file.

SlAM J. COMPUT. 1982 Society for Industrial and Applied Mathematics
Vol. 11, No. 4, November 1982 0097-5397/82/1104-0005 $01.00/0

HAMILTON PATHS IN GRID GRAPHS*

ALON ITAI’, CHRISTOS H. PAPADIMITRIOU AND JAYME LUIZ SZWARCFITER

Abstract. A grid graph is a node-induced finite subgraph of the infinite grid. It is rectangular if its set
of nodes is the product of two intervals. Given a rectangular grid graph and two of its nodes, we give
necessary and sufficient conditions for the graph to have a Hamilton path between these two nodes. In
contrast, the Hamilton path (and circuit) problem for general grid graphs is shown to be NP-complete.
This provides a new, relatively simple, proof of the result that the Euclidean traveling salesman problem
is NP-complete.

Key words. Hamilton circuit, Hamilton path, grid graphs, rectangular grid graphs, NP-complete
problem, Euclidean traveling salesman problem

1. Introduction. Let G be the infinite graph whose vertex set consists of all

.
points of the plane with integer coordinates and in which two vertices are connected
if and only if the (Euclidean) distance between them is equal to 1. A grid graph is a
finite, node-induced subgraph of G Thus, a grid graph is completely specified by
its vertex set. Let vx and vy be the coordinates of the vertex v. We say that vertex v
is even if vx + vy --0 (mod 2); otherwise, v is odd. It is immediate that all grid graphs
are bipartite, with the edges connecting even and odd vertices.
Let R(m,n) be the grid graph whose vertex set is V(R(m,n))={v: l<=v<=m
and 1 <-vy <=n}. A rectangular graph is a grid graph which, for some m and n, is
isomorphic to R (m, n). Thus m and n, the dimensions, specify a rectangular graph
up to isomorphism.
Let s and be distinct vertices of a graph G. We say that the Hamilton path
problem (G, s, t) has a solution if there exis{s a Hamilton path from s to in G. In
this paper we examine the Hamilton path problem for grid graphs; rectangular grid

.
graphs were examined first in [LM]. In 2 we show that the Hamilton path and
Hamilton circuit problems for general grid graphs are NP-complete. Consider now a
bipartite graph B=(VU V1),E). If Ivl-lvll/x, then all Hamilton paths of B
must start and end at vertices of V If (R (m, n), s, t), with m x n Odd, has a solution,
then the number of even vertices is greater by one than that of the odd vertices.
Hence, a necessary condition for the solvability of (R (m, n), s, t) is that both s and
be even. In 3 it is shown that this condition is also sufficient for nontrivial (i.e.,
m, n > 1) odd rectangular graphs. If m x n is even, then a solution is possible only if
s and have different parity. However, this condition is not sufficient. There are three
families of configurations for which even though s and have different parity
(R(m, n),s, t) has no solution. In 3 we give the precise necessary and sufficient
conditions for a Hamilton path problem to have a solution. Partial results in this
direction were first proved in [LM].

* Received by the editors September 22, 1980, and in final form August 25, 1981.

" Department of Computer Science, Technion, Haifa, Israel. Part of this work was conducted while
this author was visiting the Electrical Engineering and Computer Science Department, University of
California at Berkeley, and the Laboratory for Computer Science, Massachusetts Institute of Technology.
$ Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, Massachusetts
02139, and National Technical University of Athens, Greece. The work of this author was supported by
the National Science Foundation under grant MCS 76-01193.
Universidade Federal do Rio de Janeiro, Brasil. Present address: Computer Science Division,
University of California, Berkeley, California 94720. The work of this author was supported by the Conselho
Nacional de Desenvolvimento Cientifico e Technologico (CNPq), Brasil, processo 574/78.

676
 HAMILTON PATHS IN GRID GRAPHS 677

2. NP-completeness. Before showing that finding Hamilton paths and circuits in

grid graphs is NP-complete, we first show several lemmas"
LEMMA 2.1. The Hamilton circuit problem for planar bipartite graphs with
maximum degree 3 is NP-complete.
Proof. The Hamilton circuit problem is NP-complete for planar digraphs such
that for all vertices v"
indegree (v) + outdegree (v) 3 (see [GJ], [P]).
To prove the lemma, we conduct for all vertices v the appropriate transformation as
illustrated in Fig. 2.1. The resulting graph is planar (the digraph was), bipartite and
has maximum degree less than or equal to 3. 1-1

FIG. 2.1

Let B (VU V 1, E) be a bipartite graph, G1 a rectangular grid graph and let

emb be a one-to-one function from VLI V to the vertices of G1 and from E to
,
paths in G1. We say that emb is a parity-preserving embedding of B into G1 if:
1. The vertices V are mapped to even vertices of G1. (If v V then emb (v)
is even.)
2. The vertices of V are mapped to odd vertices of G1. (If v V 1, emb (v) is odd.)
3. The edges of B are mapped to vertex-disjoint (except perhaps for endpoints)
paths of G1 (i.e., if vu E(B), then emb (vu) is a path P from emb (v) to emb (u),
and the intermediate vertices of P do not belong to any other path).
See Fig. 2.2 for an example of a parity-preserving embedding.
LEMMA 2.2. If B is a bipartite planar graph with n vertices and maximum degree
3, then we can construct in polynomial time a parity preserving embedding of B into a
rectangular graph R (kn, kn (for some constant k ).
Proof. It is a quite well-known and straightforward result (see, for example, [S],
[V]) that all cubic planar graphs with n nodes can be embedded in R (n, n). Our extra
requirement, preserving parity, can be accommodated by multiplying the scale by 3
and moving the vertices "locally" as in Fig. 2.3. lq

Yl x3
Xl Yl

x2 Y2 emb

x3
Y5
FIG. 2.2
678 ALON ITAI, CHRISTOS H. PAPADIMITRIOU AND JAYME LUIZ SZWARCFITER

o
v

o o

FIG. 2.3

,
P4
e4-, P3
e3

FIG. 2.4

a b
[--1

b
o
111 !!111d
c b2= c ,, ild
11
ds= d2
Cl.._
c4=b 5 c3 d3:d 4
(a) %!!i ill

(b)
FIG. 2.5

To show NP-completeness of the Hamilton circuit problem for grid graphs, we

shall transform an arbitrary planar, bipartite, cubic graph B into a grid graph. Each
vertex of B will correspond to a 9-cluster, the nine vertices of a square of size 2
(Fig. 2.4).
LEMMA 2.3. Let C9 be a 9-cluster, as in Fig. 2.4. Then for all 1 <-_i !" <--4, there
exists a Hamilton path from pi to p which contains all four edges (e e2, e3, e4}.,
Proof. By inspection.
A strip is a rectangular graph with minimum dimension 2 (Fig. 2.5a). The strip

T: S(a, b; c, d) t.JS(a, b; c, d)
such that both
.
with corners a, b, c, d (a is adjacent to b and c is adjacent to d) is denoted S (a, b; c, d).
A tentacle T is a grid graph which is a union of a series of strips,
S(a, b c, d),

ci, di V(S(ai+l, bi+l; c+, d+)), 1,.. ,k 1

 HAMILTON PATHS IN GRID GRAPHS 679

and one of
ai+l, bi+l V(S(ai, bg; c, dg)), 1,. ., k 1;
there is no other intersection between the vertex sets of the strips; and each edge of
T belongs to one of the S’s.
From the definition the overlap must be in the corners of the strips as in Fig. 2.5a.
The vertices a 1, b 1, ck, dk are the corners of T.
LEMMA 2.4. Let s and be corners of a tentacle T. There is a HP from s to in
T if and only if s and have different parity.
Proof. By an easy induction on the number of strips.
THEOREM 2.1. The Hamilton circuit problem for grid graphs is NP-complete.
Proof. Given a planar, degree <-3, bipartite graph B, we shall construct a grid
graph G9 such that G9 has a Hamilton circuit if and only if there exists a Hamilton
circuit in B.
First we embed B in a grid graph G1, as in Lemma 2.2. The graph G9 will be
an induced subgraph of the grid resulting by multiplying the scale of G1 by 9. Each
image of a vertex w (wx, wy) of B corresponds to the following 9-cluster of G9:
{z [wx <- Zx <= w + 2, wy <= z <- w + 2}.
The edges of B are simulated by tentacles. Suppose vu is an edge leading from
v V(B) to u VI(B). Consider the path in G1 corresponding to vu. G9 will include
the blown up image of this path and another layer to obtain a tentacle. Some care
must be taken as to how the tentacle is connected to the 9-clusters corresponding to
v and u. By the construction the corners of the 9-cluster corresponding to v are all
even. If in G1 vu leaves v from below, then the corresponding tentacle is connected

,
as in Fig. 2.6a (recall that v is even). The other cases are symmetric (just rotate the
figure 90 180 or 270). Since u is odd the connection is completed as in Fig. 2.6b.
This concludes the description of G9. An example is shown in Fig. 2.8.

o @ o
V @ 0
@ o @ /
0
0 @ 0
o U ""
V
’
o
o

o
V**
U o
o
o
G 0

(9 GI G9
(a) (b)
FIG. 2.6

By Lemma 2.4 a tentacle Tuv can be covered by two Hamilton paths" the cross
path from v* to u* (Fig. 2.7a) and the return path from v* to v** (Fig. 2.7b).
The following two claims complete the proof of the theorem.
CLAIM 1. Let HCB be a Hamilton circuit in B. Then there exists a Hamilton circuit
nc9 in G9.
Proof. HC9 is constructed as follows: If vu HCB, the tentacle Tuv is covered in
HC9 by a cross path; otherwise, it is covered by a return path. The clusters themselves
680 ALON ITAI, CHRISTOS H. PAPADIMITRIOU AND JAYME LUIZ SZWARCFITER

o o o o
o o

o o o
0 0

,retu rn path cross path

FIG. 2.7

X3

Y3
FIG. 2.8
 HAMILTON PATHS IN GRID GRAPHS 681

are covered as in Lemma 2.3. The partial paths can be connected to constitute a
Hamilton circuit. (Some edges of type ei in Fig. 2.4 must be deleted.)
CLAIM 2. If HC9 is a Hamilton circuit in G9, then there exists a Hamilton circuit
HCB in B.
Proof. By construction each tentacle Tvu is covered either by a cross path or by
a return path (connected to v). CB consists of all edges corresponding to tentacles
covered by cross paths. This is a Hamilton circuit because each 9-cluster cannot be
covered by HC unless it is incident upon exactly two cross paths.
COROLLARY 1. The Hamilton path problem for grid graphs is NP-complete.
Proof. Reduction from the Hamilton circuit problem for grid graphs. Let G be
a grid graph without degree-1 nodes. Since it is finite, it must have a vertex s of
degree 2. Let be any of the neighbors of s. Then (G, s, t) has a solution if and only
if G has a Hamilton circuit, fi
By adding two nodes of degree 1 to G, we may also conclude that the Hamilton
path problem without specified endpoints is NP-complete.
A rectangular subgrid graph is a subgraph (not necessarily induced) of G that
has V(R (m, n)) as its vertices for some m, n > 0.
COROLLARY 2. The Hamilton circuit and path problems for rectangular subgrid
graphs are NP-complete.
Sketch of proof. The grid graph constructed in the proof of the theorem may be
considered as a rectangular one minus certain "holes". We can now "fill" these holes
with long paths so as to transform the graph into a rectangular subgrid one. 71
The Euclidean version of the traveling salesman problem was proved NP-complete
in [Pa]. It is interesting, however, to notice that the Hamilton circuit problem for grid
graphs is a special case of the Euclidean traveling salesman problem, with cities the
nodes of the grid graph and with length of the tour equal to the number of nodes.
We therefore have:
COROLLARY 3. The Euclidean traveling salesman problem is NP-complete.
We notice that this proof is much simpler than that in [Pa]. It also avoids an
annoying complication having to do with the precision in which the distances are
calculated (see [Pa]).

3. Hamilton path problems in rectangular graphs.

3.1. Necessary conditions. Let B (Vk3 V 1, E) be a bipartite graph with [V[ _->
IV1[. We will think of the vertices of B as colored by two colors, black and white.
All the vertices of V will be colored by one color, the ma/ority color, and the vertices
V by the minority color.
The Hamilton path problem (B, s, t) is color compatible if
(1) B is even (Ivl- Ivl[) and s and have different color or
(2) is odd (ivl- Iw l/ 1) and s and are colored by the majority color (i.e.,
s, V).
Since the vertices of any Hamilton path alternate between the two colors, color
compatibility is a necessary condition for the existence of a Hamilton path. Another
source of necessary conditions arises from the connectivity of the graph. If s or is
a separating vertex (i.e., G-{s} or G-{t} is not connected), then there exists no s,
Hamilton path in G. For rectangular graphs this implies the following conditions for
the graph to have no s, Hamilton path.
(F1) G is a 1-rectangle, and either s or is not a corner (Fig. 3.1a).
Also, no s, Hamilton path exists if {s, t} is a separating pair, i.e., G-{s, t} is not
connected. For rectangular graphs this implies
682 ALON ITAI, CHRISTOS H. PAPADIMITRIOU AND JAYME LUIZ SZWARCFITER

o o o o @ o o
@ 0 0
(a)
(b)

0 0 @ 0 0 0 0
s
o o o 0 0 0
0 0 0 0 0 0
$
(d)
FIG. 3.1

(F2) G is a 2-rectangle, and st is a nonboundary edge (i.e., st is an edge, and it

is not on the outermost face, see Fig. 3.1b).
Consider Fig. 3.1c or 3.1d. The vertices s and are color compatible, the
connectivity is greater than two, but still there is no s, Hamilton path. These cases
can be generalized to yield the following condition:
(F3) (G, s, t) is isomorphic to (G’, s’, t’) which satisfies:
1. G’= R (m, n) with n 3 and m even.
2. s’ is colored differently from t’ and the left corners of G’.
3. Sx’ < t’ 1 (Fig. 3. lc) or s 2 and s < tx (Fig. 3. ld).
A Hamilton path problem (G, s, t) is forbidden if it satisfies one of the conditions
(F1), (F2) and (F3).
LEMMA 3.1. If (G, s, t) is forbidden, then there exists no Hamilton path from s to
rinG.
The proof is a straightforward case analysis. ]
We summarize this section with the following definition and theorem:
A Hamilton path problem (G, s, t) is acceptable if it is color compatible and not
forbidden.
THEOREM 3.1. If there exists an s, tHamilton path in G, then (G, s, t) is acceptable.
3.2. Sufficient conditions. In this section it is shown that all acceptable HP
problems have solutions (i.e., acceptability is sufficient). The method of proof is to
break large acceptable HP problems into disjoint acceptable subproblems, the HPs
of which can be used to construct an HP for the original problem. The two methods,
stripping and splitting, are discussed in the following subsection. We will be done if
we show that for prime problems (those which cannot be stripped or split) acceptability
implies solvability. However, since the size of these problems is small, their number
is finite and can be handled by a case analysis ( 3.2.2).
3.2.1. Stripping and splitting. A separation of a rectangle R is a partition of R
into two subrectangles, i.e., V(R) is a disjoint union of V(R) and V(R2).
A strip S strips a Hamilton path problem (R, s, t) if
1. S, R -S is a separation of R,
2. s,tR-S,
3. (R -S, s, t) is acceptable.
LEMMA 3.2.1. Let (R, s, t) be an acceptable Hamilton path problem and S strips
R. If (R -S, s, t) has a solution, then (R, s, t) also has a solution.
Proof. Let P be a Hamilton path of R -S. Then there exists an edge pq P such
that pq is on the boundary of R- S facing S. A Hamilton path for (R, s, t) can be
obtained by the construction illustrated in Fig. 3.2.
 HAMILTON PATHS IN GRID GRAPHS 683

q q
R-S s R-S
(a) (b)
FIG. 3.2

Let R (m, n) be a rectangle with m >= n. v, w V(R (m, n)) are called antipodes if
Vx<-2 and Wx>=m-1.
LEMMA 3.2.2. Let (R (m, n), s, t) be an acceptable Hamilton path problem which
cannot be stripped (by any strip S) and 2 <-n <-re(n, m) (4, 5), (4, 4). Then s and
are antipodes.
Proof. Without loss of generality, let sx <- tx. Let S be the leftmost strip of R (i.e.,
V(S) {v V(R): vx -< 2}). It suffices to show that s e S. Assume to the contrary that
s S. Let Hs, be the rectangle resulting from deleting S from R. A contradiction will
be obtained if (ns.t, s, t) is acceptable. Note that (Hs, t, s, t) is color compatible. Now
we must show that it is not forbidden.
Case 1. n x m is odd. Hs.t is also odd, so it cannot be forbidden.
Case 2. m > 5, n > 3. Both the dimensions of Hs.t are greater than 3, so it cannot
be forbidden.
Case 3. n 3, m > 5. If (Hs.,, s, t) is forbidden, it must be F3, but then so is (R, s, t).
Case 4. n 2. Since (R, s, t) is not forbidden, neither is (Hs.t, s, t). Note that if
m 5, (Hs.t, s, t) may be F3, but in this case (R, s, t) is F2.
Case 5. m 4, n 3. The only possibility for (H,t, s, t) to be forbidden is depicted
in Fig. 3.3b. However, then (R, s, t) satisfies F3. ]
Let (R, s, t) be an acceptable Hamilton path problem and pq an edge. pq splits
(R, s, t) if there exists a separation of R to Rp and Rq such that:
1. s, p Rp and (R, s, p) is acceptable, and
2. q, Rq and (Rq, q, t) is acceptable.
The following lemma follows immediately from the definition of splitting.
LEMMA 3.2.3. Let pq be an edge which splits (R,s, t). If both (Rp, s, p) and
(Rq, q, t) have a solution, then so does (R, s, t).
3.2.2. Prime problems. A Hamilton path problem (R, s, t) is prime if it cannot
be stripped or split. The following lemma allows us to confine the discussion to a
finite number of cases.
LMMA 3.2.4. Let (R (m, n ), s, t) be an acceptable prime Hamilton path problem,
then (n, rn) (4, 5) or n, m <- 3.

0 0 e
0 0 s
0 o
0 I0 0
0 0

FIG. 3.3
684 ALON ITAI, CHRISTOS H. PAPADIMITRIOU AND JAYME LUIZ SZWARCFITER

Rp Rq
FIG. 3.4

Proof. Assume first that (n, m) {(4, 4), (4, 5)}. Then s and are antipodes. Let S
be the leftmost strip, then s e S. We show that there exists a split such that Rp S.
Case 1. m > 5, n > 4. There are at least two vertices, v i, with v ix 2, 1, 2 and
colored differently than s. Let p be a v not connected to s by a nonboundary edge
of S and q be the adjacent vertex in R -S. The edge pq splits R" Rp S, and (Rp, s, p)
is acceptable by the construction. As for (Rq, q, t), q # t, since tx >= m 1 > 3 q, since
s and q have the same color, (Rq, q, t) is color compatible; Rq has dimensions
(m 2, n) > 3; hence, (Rq, q, t) is not forbidden and, therefore, is acceptable.
Case 2. m > 5, n 3 (Fig. 3.5a). Without loss of generality, the left corners of
R are white. Let p (2, 1) and q (3, 1). We show that edge pq splits (R, s, t). Note
that p is black and q is white. If m is even, then s is white and black; otherwise
(R, s, t) is not acceptable. Therefore p # s and q t. Consequently (Rp, s, p) and
(Rq, q, t) are color compatible. If m is odd, then both s, are white. Therefore p # s,
and because qx 3 < tx, also q t. Again, (Rp, s, p) and (Rq, q, t) are color compatible.
In both cases p is a corner of Rp and q a corner of Rq. Hence, the subproblems are
not forbidden.

SO 0 0 0’|0 0

o!o 0 so O,O
P0q
0 .O
O 0 0
Iq
(a) (b)
0 O O0

0 0 I SO

Rp oo Rq o
soe ot Rp Rq
;0 0

(c) (d)

H st
0 OI 0
Rp SO
R-Hst
(e) f)

0 olo
OI 0 po oqo
SO 0 0

(h)

FIG. 3.5
 HAMILTON PATHS IN GRID GRAPHS 685

Case 3. n 3 (Fig. 3.5b). Without loss of generality s is white. The edge pq

(2, 1)(3, 1) splits (R, s, t) q since q is white and is black.
Case 4. m 5, n 5 (Fig. 3.5c). Let p be a black vertex not connected to s such
that px 2, q (px + 1, p). Since Rq is odd, pq splits (R, s, t).
Case 5. m 5, n 3 (Fig. 3.5d). Similar to Case 4.
Case 6. m =4, n =4. If s and are antipodes, then either (2, 1)(3, 1) or
(2, 4)(3, 4) splits (R, s, t) (Fig. 3.5e). If s and are not antipodes, we may assume
that SxSy, tx, tr =<2. Therefore, either the rightmost or the uppermost strip may be
stripped off (R, s, t) (Fig. 3.50.
Case 7. m =4, n =3.
If s is white, then pq (2, 1)(3, 1) splits (R, s, t) (Fig. 3.5g). Otherwise, s is black
and sx 2, t 3. Therefore, (2, 2)(3, 2) splits (R, s, t) (Fig. 3.5h). I-1
LEMMA 3.2.5. Any (R (5, 4), s, t) acceptable Hamilton path problem is solvable.
Proof. It suffices to prove the lemma for prime problems. First, s and cannot
be antipodes. If they were, either edge, (2, 1)(3, 1) or (2, 4)(3, 4), splits (R, s, t). We
can then assume that both s, do not belong, say, to the rightmost strip. Now, if one
of s, belongs to the lowermost strip and the other to the uppermost, then either edge
(4, 2)(4, 3) or (5, 2)(5, 3) splits (R, s, t). Therefore without loss of generality we can
restrict to the case sx, tx <-3 and s, tr-< 2. Then the rightmost strip can be stripped
off, except when (R, s, t) is isomorphic to the problem of Fig. 3.6. That is a prime
problem, solvable as indicated in the figure.

FIG. 3.6

LEMMA 3.2.6. If (R, s, t) is an acceptable prime Hamilton path problem, then it

is solvable.
Proof. From Lemmas 3.2.4 and 3.2.5, we may assume that n, m -< 3. For all values
of m and n, all nonisomorphic problems and their corresponding paths are illustrated
in Fig. 3.6.

Case 1. re=n=3.

Case 2. n =2, m =3.

Case 3. n =2, m =2.

 686 ALON ITAI, CHRISTOS H. PAPADIMITRIOU AND JAYME LUIZ SZWARCFITER

Following the discussion at the beginning of this section, the preceding lemmas
yield the following:
THEOREM 3.2. There exists a Hamilton path from s to in R if and only if (R, s, t)
is acceptable.
3.3. An algorithm. The proof of Theorem 3.2 is constructive. To decide whether
a Hamilton path problem (R(n, m),s, t) has a solution, we check whether it is
acceptable. This requires time linear with the representation of n, m, s and t. To find
the path itself, we first try to strip off the strips, constructing partial paths, and try to
split the problem. This process is repeated until we are left with prime problems, for
which a path can be found in constant time. The partial paths are pasted together as
in Lemmas 3.2.1, 3.2.3. The entire process takes time linear in the length of the path,

[AHU] A. V. AHO, J. E. HOPCROFT

REFERENCES
-
O(nm). We note here that the results of this and the previous section leave open the
question whether the Hamilton circuit problem is polynomial for grid graphs that are
not rectangular, but neither have "holes", i.e., both G and G G are connected.

AND J. D. ULLMAN, The Design and Analysis of Computer

Algorithms, Addison-Wesley, Reading, MA., 1974.
[GJ] M.R. GAREY AND O. S. JOHNSON, Computers and Intractability: A Guide to the Theory of
NP-Completeness, Freeman, San Francisco, CA, 1979.
[GJT] M.R. GAREY, D. S. JOHNSON AND R. E. TARJAN, The planar Hamilton circuit problem is
NP-complete, this Journal, 5 (1976), pp. 704-714.
[K1] R.M. KARP, Reducibility among combinatorial problems, in Complexity of Computer Computa-
tions, R. E. Miller and J. W. Thatcher, eds., Plenum Press, New York, 1972, pp. 85-104.
[K2] M.S. KRISHNAMOORTHY, An NP-hard problem in bipartite graphs, SIGACT News, 7 (1975), 1,
26.
[LM] F. LuccIo AND C. MUGNAI, Hamiltonian paths on a rectangular chessboard, 16th Annual Allerton
Conference, 1978, pp. 73-78.
[Pa] C.H. PAPADIMITRIOU, The Euclidean traveling salesman problem is NP-complete, Theoret. Comp.
Sci., 4 (1977), pp. 237-244.
[P] J. PLESNIK, The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree
two, IPL, to appear.
[S] Y. SHILOACH, Linear and planar arrangements of graphs, Ph.D. dissertation, Appl. Math. Dept.,
Weizmann Institute of Science, Rehovot, Israel, 1976.
IV] L.G. VALIANT, unpublished manuscript, 1979.

View publication stats