Equivalence of Local Treewidth and Linear Local Treewidth and its Algorithmic Applications
Erik D. Demaine
Abstract
We solve an open problem posed by Eppstein in 1995 [14, 15] and re-enforced by Grohe [16, 17] concerning locally bounded treewidth in minor-closed families of graphs. A graph has bounded local treewidth if the subgraph induced by vertices within distance r of any vertex has treewidth bounded by a function of r (not n). Eppstein characterized minor-closed families of graphs with bounded local treewidth as precisely minor-closed families that minor-exclude an apex graph, where an apex graph has one vertex whose removal leaves a planar graph. In particular, Eppstein showed that all apex-minor-free graphs have bounded local treewidth, but his bound is doubly exponential in r, leaving open whether a tighter bound could be obtained. We improve this doubly exponential bound to a linear bound, which is optimal. In particular, any minor-closed graph family with bounded local treewidth has linear local treewidth. Our bound generalizes previously known linear bounds for special classes of graphs proved by several authors. As a consequence of our result, we obtain substantially faster polynomial-time approximation schemes for a broad class of problems in apex-minor-free graphs, improving the running time from 22
2O (1/)

MohammadTaghi Hajiaghayi
for maximization problems. Eppstein [15, 14] further generalized Baker's approach by replacing local regions of bounded outerplanarity with local regions of bounded treewidth. The resulting approximation algorithms apply to any graph of bounded local treewidth, a notion newly introduced by Eppstein [14, 15]. A graph has bounded local treewidth if the treewidth of the subgraph induced by the set of vertices at distance at most r from any vertex is bounded above by some function f (r) independent of n. Eppstein also characterized all minor-closed families of graphs that have bounded local treewidth, showing that they are precisely apex-minor-free graphs, where an apex graph has a vertex whose removal leaves a planar graph. For example, K3,3 and K5 are apex graphs, and therefore apex-minor-free graphs, or equivalently graphs of bounded local treewidth, include planar graphs as a special case. Eppstein's approach returns to the realm of impracticality, because his bound on local treewidth in a general apexO (r ) . Eppminor-free graph is doubly exponential in r: 22 stein [15] improved this bound to linear--O(r)--for the special case of bounded-genus graphs, which are apex-minorfree [14]. This linear bound on local treewidth was later established for the special cases of K3,3 -minor-free and K5 minor-free graphs [19], and then for single-crossing-minorfree graphs [12, 11]. A graph is single-crossing if it can be embedded in the plane with at most one crossing; thus, every single-crossing graph is an apex graph. Grohe [17] also established a linear bound on local treewidth for "apex-free almost-embeddable graphs"; see Section 2.4 for a definition. In this paper, we prove that every apex-minor-free graph has linear local treewidth, generalizing all results of the previous paragraph. This result solves an open problem posed by Eppstein [15, 14] and mentioned in [12, 16, 17]. As a consequence, we obtain the surprising result that every minor-closed family of graphs with bounded local treewidth in fact has linear local treewidth. Along the way, we reprove Eppstein's characterization of minor-closed families of graphs with bounded local treewidth. We recommend reading Section 4, which gives the intuition and high-level overview of the (difficult) proof of this result and the techniques involved. This intuition is intended to make sense (at a high level) even while skipping over the definitions in Sections 2 and 3. Using our combinatorial results, we obtain substan-

nO(1) to 2O(1/) nO(1) .

1 Introduction Many problems are inapproximable beyond (log n) or (n ) factors for general graphs, yet for classes of graphs with additional structural properties, we can obtain polynomial-time approximation schemes (PTAS). The first collection of results along these lines was for planar graphs [21]. These results were later generalized to H -minor-free graphs for any fixed graph H [2]. Both of these results are impractical; for example, just to achieve an approximation ratio of 2, the base case of the planar-graph approach requires 400 exhaustive solution of graphs of up to 22 vertices [8]. To address this impracticality, Baker [4] introduced a practical approach for planar graphs based on decomposition into overlapping subgraphs of bounded outerplanarity. Specifically, Baker's approach obtains (1 + )-approximation algorithms with running times of 2O(1/) nO(1) for many problems on planar graphs, such as maximum independent set, minimum dominating set, and minimum vertex cover. Chen [7] later generalized Baker's approach to obtain PTASs for K3,3 -minor-free graphs and K5 -minor-free graphs, but only
 Laboratory for Computer Science, Massachusetts Institute of Technology, 200 Technology Square, Cambridge, MA 02139, U.S.A., {edemaine,hajiagha}@theory.lcs.mit.edu

Copyright © 2004 by the Association for Computing Machinery, Inc. and the Society for industrial and Applied Mathematics. All Rights reserved. Printed in The United States of America. No part of this book may be reproduced, stored, or transmitted in any manner without the written permission of the publisher. For information, write to the Association for Computing Machinery, 1515 Broadway, New York, NY 10036 and the Society for Industrial and Applied Mathematics, 3600 University City Science Center, Philadelphia, PA 19104-2688

840


tially faster PTASs, improving the running time from 2 n to 2 n , for many problems including hereditary maximization problems (e.g., maximum independent set), maximum triangle matching, maximum H matching, maximum tile salvage, minimum vertex cover, minimum dominating set, minimum edge-dominating set, and subgraph isomorphism for a fixed pattern. We also substantially improve the running time of a key step in the general framework of [16] for deciding first-order properties about graphs of bounded local treewidth. Grohe [17] developed PTASs for a few problems in the list above for graphs excluding a fixed minor H (not just when H is an apex graph). The running time of these algorithms includes a factor of nf (H ) for a function f . In contrast, the running times of our algorithms replace this factor with n3+ for any  > 0, thus separating the dependence on n and H . (Both algorithms have another factor of the form g (H, ) where 1 +  is the approximation ratio.) Finally, it is worth metioning that recently approximation algorithms for H -minor-free graphs for a fixed graph H have been studied extensively; see e.g. [5, 18, 6, 20, 22]. In particular, it is generally believed that several algorithms for planar graphs can be generalized to H -minor-free graphs for any fixed H [18, 20, 22]. In fact, the main reason is that H minor-free graphs are very general; the deep Graph-Minor Theory of Robertson and Seymour shows that any graph class that is closed under minors is characterized by excluding a finite set of minors. This paper is organized as follows. Sections 2 and 3 introduce the terminology and basic concepts used throughout the paper. In particular, Section 3 introduces the necessary concepts and some of the main results from the Robertson and Seymour Graph Minor Theory. Section 4 provides a high-level description of our combinatorial results and their proof. Section 5 describes the many algorithmic applications of this combinatorial result, which use additional nonstandard tricks to improve running time. Section 6 establishes several structural results about graphs with bounded local treewidth and linear local treewidth. Section 7 gives a morein-depth description of the proof of our combinatorial results. The full details of some of our lemmas share several components with the Graph Minor Theory, which is a long series of long papers. Therefore, we limit ourselves in this extended abstract to an intuitive description of the proofs of a few lemmas that cannot be directly obtained from the Graph Minor Theorems. The reader is referred to [10] to see more details. Finally, we conclude with some remarks and open problems in Section 8. 2 Background 2.1 Preliminaries. All the graphs in this paper are undirected without loops or multiple edges. Our graph terminol22
O (1/)

O (1)

O (1/) O (1)

ogy is as follows. A graph G is represented by G = (V , E ), where V (or V (G)) is the set of vertices and E (or E (G)) is the set of edges. We denote an edge e between u and v by {u, v }. We define n to be the number of vertices of a graph when this is clear from context. The (disjoint) union of two disjoint graphs G1 and G2 , G1  G2 , is the graph G with merged vertex and edge sets: V (G) = V (G1 )  V (G2 ) and E (G) = E (G1 )  E (G2 ). We define the r-neighborhood of a set S  V (G), denoted by r NG (S ), to be the set of vertices at distance at most r from at least one vertex of S ; if S = r we simply use the notation r r NG (v ). For the ease of notation, we often use NG (v ) instead r of G[NG (v )] when it is clear from the context. One way of describing classes of graphs is by using minors, introduced as follows. Contracting an edge e = {u, v } is the operation of replacing both u and v by a single vertex w whose neighbors are all vertices that were neighbors of u or v , except u and v themselves. A graph G is a minor of a graph H if H can be obtained from a subgraph of G by contracting edges. A graph class C is a minor-closed class if any minor of any graph in C is also a member of C . A minor-closed graph class C is H -minor-free if H  C . For example, a planar graph is a graph excluding both K3,3 and K5 as minors. 2.2 Treewidth and local treewidth. The notion of treewidth was introduced by Robertson and Seymour [25] and plays an important role in their fundamental work on graph minors. To define this notion, first we consider the representation of a graph as a tree called tree decomposition. More precisely, a tree decomposition of a graph G = (V , E ), denoted by T D(G), is a pair (, T ) in which T = (I , F ) is a tree and  = {i |i  I } is a family of subsets of V (G) such i that: (1) I i = V ; (2) for each edge e = {u, v }  E there exists an i  I such that both u and v belong to i ; and (3) for all v  V , the set of nodes {i  I |v  i } forms a connected subtree of T . To distinguish between vertices of the original graph G and vertices of T in T D(G), we call vertices of T nodes and their corresponding i 's bags. The maximum size of a bag in T D(G) minus one is called the width of the tree decomposition. The treewidth of a graph G (tw(G)) is the minimum width over all possible tree decompositions of G. A tree decomposition is called a path decomposition if T = (I , F ) is a path. The pathwidth of a graph G (tw(G)) is the minimum width over all possible path decompositions of G. A branch decomposition of a graph (or a hyper-graph) G is a pair (T ,  ), where T is a tree with vertices of degree 1 or 3 and  is a bijection from the set of leaves of T to E (G). The order of an edge e in T is the number of vertices v  V (G) such that there are leaves t1 , t2 in T in different components of T (V (T ), E (T ) - e) with  (t1 ) and  (t2 ) both containing v as an endpoint. The width of (T ,  ) is the maximum order over all edges of T , and the branchwidth of G, bw(G), is the

841


minimum width over all branch decompositions of G. For many NP-complete problems, we can derive polynomial-time algorithms restricted to graphs of bounded treewidth using a general dynamic-programming approach similar to that on trees [3]. However, still the class of graphs of bounded treewidth is of limited size; we would like to solve NP-complete problems for wider classes of graphs. As mentioned before, Baker [4] developed several approximation algorithms to solve NP-complete problems for planar graphs. To extend these algorithms to other graph families, Eppstein [15] introduced the notion of bounded local treewidth, defined formally below, which is a generalization of the notion of treewidth. D E FI N I T I O N 2 . 1 . The local treewidth of a graph G is the function ltwG : N  N that associates with every r  N the maximum treewidth of an r-neighborhood in G. We r set ltwG (r) = maxvV (G) {tw(G[NG (v )])}, and we say that a graph class C has bounded local treewidth (or locally bounded treewidth) when there is a function f : N  N such that for all G  C and r  N, ltwG (r)  f (r). A class C has linear local treewidth if there are constants c, d  R such that ltwG (r)  cr + d for all G  C , r  N. Eppstein [15] showed that a minor-closed graph class E has bounded local treewidth if and only if E is H -minor free for some apex graph H . 2.3 Clique Sums. Suppose G1 and G2 are graphs with disjoint vertex-sets and k  0 is an integer. For i = 1, 2, let Wi  V (Gi ) form a clique of size k and let Gi (i = 1, 2) be obtained from Gi by deleting some (possibly no) edges from Gi [Wi ] with both endpoints in Wi . Consider a bijection h : W1  W2 . We define a k -sum G of G1 and G2 , denoted by G = G1 k G2 or simply by G = G1  G2 , to be the graph obtained from the union of G1 and G2 by identifying w with h(w) for all w  W1 . The images of the vertices of W1 and W2 in G1 k G2 form the join set. In the rest of this section, when we refer to a vertex v of G in G1 or G2 , we mean the corresponding vertex of v in G1 or G2 (or both). It is worth mentioning that  is not a well-defined operator and it can have a set of possible results. The following lemma whose intuition will play an important role in our results shows how the treewidth changes when we apply a clique-sum operation. L E M M A 2 . 1 . ( [ 1 9 ] ) For any two graphs G and H , tw(G  H )  max{tw(G), tw(H )}. 2.4 Clique-sum decompositions of H -minor-free graphs. Our result uses the deep theorem of Robertson and Seymour on graphs excluding a non-planar graph as a minor. Intuitively, Robertson-Seymour's theorem says for every graph H , every H -minor-free graph can be expressed as a tree-structure of "pieces", where each piece either has bounded size or is a graph which can be drawn in a surface

in which H cannot be drawn, except for a bounded number of "apex" vertices and a bounded number of "local areas of non-planarity" called vortices. Here the bounds only depend on H . Roughly speaking we say a graph G is h-almost embeddable in a surface S if there exists a set X of size at most h of vertices, called apex vertices or apices, such that G - X can be obtained from a graph G0 embedded in S by attaching at most h graphs of pathwidth at most h to G0 along the boundary cycles C1 , · · · , Ch in an orderly way. More precisely: D E FI N I T I O N 2 . 2 . A graph G is h-almost embeddable in S if there exists a vertex set X of size at most h called apices such that G - X can be written as G0  G1  · · ·  Gh , where 1. G0 has an embedding in S ; 2. the graphs Gi , called vortices, are pairwise disjoint; 3. there are faces F1 , . . . , Fh of G0 in S , and there are pairwise disjoint disks D1 , . . . , Dh in S , such that for i = 1, . . . , h, Di  Fi and Ui := V (G0 )  V (Gi ) = V (G0 )  Di ; and 4. the graph Gi has a path decomposition (Bu )uUi of width less than h, such that u  Bu for all u  Ui . We note that the sets Bu are ordered by the ordering of their indices u as points in Ci , where Ci is the boundary cycle of Fi in G0 . An h-almost embeddable graph is called apex-free if the set X of apices is empty. Now, the deep result of Robertson and Seymour is as follows. T H E O R E M 2 . 1 . ( [ 3 2 ] ) For every graph H there exists an integer h  0 only depending on |V (H )| such that every H -minor-free graph can be obtained by at most h-sums of graphs of size at most h and h-almost-embeddable graphs in some surfaces in which H cannot be embedded. In particular, if H is fixed, any surface in which H cannot be embedded has bounded genus. Thus, the summands in the theorem are h-almost-embeddable graphs in boundedgenus surfaces (In the rest of the paper, we consider bounded size pieces as almost-embeddable graphs whose bound genus parts are empty). Unfortunately, since Theorem 2.1 is very general and has appeared in print very recently, not many other applications are known. However, this structural theorem plays an important role in obtaining the rest of the results of this paper, and we believe that it can be further useful in obtaining algorithms and proving theorems on graphs excluding a fixed graph H as a minor. 3 Technical Definitions In this subsection we remind a very limited part of the machinery developed in Graph Minor papers that is used in our proofs.

842


A surface  is a compact 2-manifold, without boundary. A line in  is subset homeomorphic to [0, 1]. An O-arc is a subset of  homeomorphic to a circle. Let G be a graph 2-cell embedded in , i.e., every region in the embedding is homeomorphic to a disc. To simplify notations we do not distinguish between a vertex of G and the point of  used in the drawing to represent the vertex or between an edge and the line representing it. We also consider G as the union of the points corresponding to its vertices and edges. That way, a subgraph H of G can be seen as a graph H where H  G. We call by region of G any connected component of  - E (G) - V (G). (Every region is an open set.) We use the notation V (G), E (G), and R(G) for the set of the vertices, edges and regions of G. If   , then  denotes the closure of , and the boundary of  is b d() =    - . An edge e (a vertex v ) is incident with a region r if e  b d(r) (v  b d(r)). A subset of  meeting the drawing only in vertices of G is called G-normal. If an O-arc is G-normal then we call it noose. The length of a noose is the number of its vertices.    is an open disc if it is homeomorphic to {(x, y ) : x2 + y 2 < 1}. We say that a disc D is bounded by a noose N if N = b d(D). A graph G 2-cell embedded in a connected surface  is -representative if every noose of length <  is contractable (null-homotopic in ). A separation of a graph G is a pair (A, B ) of subgraphs with A  B = G and E (A  B ) = , and its order is |V (A  B )|. Tangles were introduced by Robertson & Seymour in [27]. A tangle of order   1 is a set T of separations of G, each of order , such that (i) for every separation (A, B ) of G of order < , T contains one of (A, B ), (B , A) (ii) if (A1 , B1 ), (A2 , B2 ), (A3 , B3 )  T then A1  A2  A3 = G. (iii) if (A, B )  T then V (A) = V (G). Let G be a graph embedded in a connected surface . A tangle T of order  is respectful if for every noose N in  with |N  V (G)| < , there is a closed disc    with b d() = N such that separation (G  , G   - )  T . Our proofs are based on the following results from Graph Minors papers by Robertson & Seymour. T H E O R E M 3 . 1 . ( ( 4 . 3 ) I N [ 2 7 ] ) Let G be a graph with at least one edge. Then there is a tangle in G of order  if and only if G has branch-width  . T H E O R E M 3 . 2 . ( ( 4 . 1 ) I N [ 2 8 ] ) Let  be a connected surface, not a sphere, let   1, and let G be a -representative graph 2-cell embedded in . Then there is a unique respectful tangle in G of order . Also in our proofs we use the notion of radial graph. Informally, the radial graph of a 2-cell embedded in  graph

G is the bipartite graph RG obtained by selecting a point in every region r of G and connecting it to every vertex of G incident to that region. However, a region maybe "incident more than once" with the same vertex, so one needs a more formal definition. A radial drawing RG is a radial graph of a 2-cell embedded in  graph G if 1. E (G)  E (RG ) = V (G)  V (RG ); 2. Each region r  R(G) contains a unique vertex vr  V (RG ); 3. RG is bipartite with a bipartition (V (G), {vr : r  R(G)}); 4. If e, f are edges of RG with the same ends v  V (G), vr  V (RG ), then e  f does not bound a closed disc in r  {v }; 5. RG is maximal subject to 1,2,3 and 4. Finally, let A(RG ) be the set of vertices, edges, and regions (collectively, atoms) in the radial graph RG . According to Section 9 of [28] (see also [29]), the existence of a respectful tangle makes it possible to define a metric d on A(RG ) as follows: 1. If a = b, then d(a, b) = 0. 2. If a = b, and a and b are interior to a contractible closed walk of radial graph of length < 2, then d(a, b) is half the minimum length of such a walk (here by interior we mean the direction in which the walk can be contracted). 3. Otherwise, d(a, b) = . We use these metrics very often in our proofs. Interestingly, this metric will be related to regular distance metric on grids, the property that we use in Lemma 7.9. 4 Local Treewidth of Apex-Minor-Free Graphs The main result of this paper which has many algorithmic applications is as follows: T H E O R E M 4 . 1 . Any apex-minor-free graph has linear local treewidth. To obtain this result, we use the general structure of H minor-free graphs given in Theorem 2.1. Also, we need the following theorem of Hajiaghayi et al. [19]: T H E O R E M 4 . 2 . ( [ 1 9 ] ) If G1 and G2 are graphs where ltwGi (r)  f (r), f (r)  0 for all r  N, and G = G1 k G2 , then ltwG (r)  f (r). Using Theorem 2.1 and Theorem 4.2, one can easily observe that we need to only prove the following theorem: T H E O R E M 4 . 3 . Each h-almost-embeddable graph in the clique-sum decomposition of an apex-minor-free graph G has linear local treewidth. The proof of Theorem 4.3 is lengthy and we delay the proof to Section 7. In the rest of this section, we mention some major ideas of the proof.

843


Our proof is based on a series of reductions, each of which uses the deep Graph Minor Theory of Robertson and Seymour. Each reduction converts a given graph into a "simpler" graph that has linear local treewidth if and only if the original graph has linear local treewidth. To achieve this equivalence, we must preserve the distances between pairs of vertices up to constant factors, thus roughly preserving the neighborhoods, and we must preserve the treewidth of these neighborhoods up to constant factors. The first reduction effectively removes the vortices from a given almost-embeddable graph. A similar technique has been used by others, e.g., [17, 31]. Next we would like to use the property that the graph is apex-minor-free; however, only the original graph is apex-minor-free, and during the clique-sum decomposition, we may have introduced extra edges when the join set was completed into a clique. We call such edges virtual edges, and all other edges actual edges. One difficulty of Theorem 2.1 is that it does not guarantee that the virtual edges can be obtained by taking a minor of the original graph, and therefore the pieces may not be apexminor-free. The second reduction overcomes this difficulty by obtaining some virtual edges by taking minors of the original graph, and removes other virtual edges which cannot be obtained, while still preserving linear local treewidth. We call the resulting graph an approximation graph of the original graph. The next steps of the proof exploit the property that the approximation graph is apex-minor-free. Intuitively, apexes in the approximation graph play the role of the apex in the minor-excluded apex graph, and therefore the boundedgenus part of the approximation graph must (roughly) minorexclude the planar part of the apex graph. For this property to be useful, the bounded-genus part of the approximation graph must be "spread out enough" in the sense of having high representativity. If the bounded-genus graph has low representativity and is not planar, we can afford to decrease its genus by removing a small noose from the bounded-genus graph and placing all its vertices into the set of apexes. If the bounded-genus graph has high representativity, we use the resulting distance metric and the apex-minor-free property to decompose the graph into a clique-sum of several almost-embeddable graphs, reintroducing vortices in a special way. The bounded-genus parts of these almost-embeddable graphs are all planar and have no vortices except for the last which may not be planar and has a bounded number of vortices. This decomposition would seem to be making negative progress; however, the new apexes of the last graph have the special property that all their neighbors are within the vortices. In one shot, it is fairly easy to show that the last graph has linear local treewidth. Finally, we deal with almost-embeddable graphs where the bounded-genus part is in fact planar (and has no vortices). We use the fact that a planar graph with treewidth w has as a minor an O(w) × O(w) grid. In contrast, Eppstein's

approach considers general graphs instead of planar graphs, in which case we can only guarantee an O(log 1/10 w) × O(log1/10 w) grid in a graph with treewidth w. This is one place where our bounds are stronger than Eppstein's, allowing us to ultimately get a linear bound (O(r)) on local O (r ) . treewidth instead of 22 5 Algorithmic Applications: PTAS Results In this section, we mention some algorithmic applications of Theorem 4.1. First, we start by hereditary maximization problem, which determine a property that if valid for an input graph is also valid for any induced subgraph of the input. For a property  , the maximum (weight) induced subgraph problem M I S P ( ) is finding a maximum (weight) induced subgraph with the property. For example, we can search for an induced subgraph of maximum size that is chordal, acyclic, without cycles of a specified length, with edges, of maximum degree d  1, bipartite or as clique [33]. According to Yannakakis almost all of these problems are NP-complete. T H E O R E M 5 . 1 . Let G be a non-negative vertex-weighted H minor-free graph for an apex graph H and let k  1 be an integer. The maximization problem MISP( ) for a hereditary property  over G has a PTAS of ratio 1 + 1/k of the optimal with worst-case running time in O(k 23.698(ck+d) |V |3+ + k T ime 11/3(ck + d), |V |)), where T ime (w, n) is the worst-case running time of WMISP( ) over an n-vertex partial w-tree whose tree decomposition is given. T ime (w, n) is nondecreasing as n increases and c and d are some constants which only depend on |V (H )| For example, for G be a non-negative vertex-weighted apex-minor-free graph, the maximum independent set problem admits a polynomial-time approximation scheme of ration 1 + 1/k with running time O(k 23.698(ck+d) |V |3+ + k 411/3(ck+d) |V |) (see the dynamic programming for this problem in [3].) In fact, the proof of Theorem 5.1 can be easily generalized for many other problems. For the sake of similarity of the proof, we only mention the general theorem. T H E O R E M 5 . 2 . Given an H -minor-free graph G, where H is an apex graph, there are PTASs with approximation ratio 1 + 1/k (or 1 + 2/k ) running in O(ck n) time (c is a constant) on graph G for hereditary maximization problems such as maximum independent set and other problems such as maximum triangle matching, maximum H -matching, maximum tile salvage, minimum vertex cover, minimum dominating set, minimum edge-dominating set, and subgraph isomorphism for a fixed pattern. Another algorithmic consequence of our results is in the context of fixed-parameter algorithms. Grohe [16] gives a general framework for deciding first-order properties of

844


graphs of bounded local treewidth. Our result implies that these graphs in fact have linear local treewidth, substantially improving the worst-case bound on the running time of a key step in this framework. This improvement fixes one (but not all) of the bottlenecks of the algorithm mentioned by Grohe [16]. 6 Linear Local Treewidth: Basic Properties In this section we start demonstrating some basic properties of local treewidth, by which we are prepared to state the proof of Theorem 4.3 in the next section. First we consider the relation between local treewidth of a graph before and after adding an edge between two nonadjacent vertices. L E M M A 6 . 1 . Let G be a graph with ltwG (r)  f (r) for all r  N. Also let G be a graph obtained by adding an edge {u, w} between two non-adjacent vertices u and v . Then ( ltwG r)  f (3r) + 1. C O RO L L A RY 6 . 1 . By adding a constant number of edges to a graph G having linear local treewidth, the resulting graph still has linear local treewidth. C O RO L L A RY 6 . 2 . If a graph G has linear local treewidth, r tw(NG (S )) is linear in r for each set S  V (G) of bounded size. The following simple lemma express the relation of local treewidth of a graph before and after contracting an edge. L E M M A 6 . 2 . Let G be a graph with ltwGi (r)  f (r) for all r  N. Let G be a graph obtained by contracting an edge {u, w}. Then ltwG (r)  f (r + 1). C O RO L L A RY 6 . 3 . By contracting a constant number of edges of a graph G which has linear local treewidth, the resulting graph still has linear local treewidth. Also we need to use the following theorem of Grohe [17] on local treewidth. T H E O R E M 6 . 1 . ( [ 1 7 ] ) Every apex-free h-almost embeddable graph G has linear local treewidth. Finally, we finish this section by stating the following lemma on treewidth after contracting all edges of a region of a bounded genus graph. L E M M A 6 . 3 . Contracting all edges of one of the faces of a bounded genus graph G embedded on a surface  changes its treewidth by at most three. 7 Proof of Theorem 4.3 In this section, we show that any piece in the clique-sum decomposition of an apex-minor-free graph has linear local

treewidth. Before starting the proof, it is worth mentioning that, in each piece G of the clique-sum decomposition of an ^ H -minor-free graph G, each vertex u of G has a correspond^ .1 We say u is the image of u. However ing vertex u in G ^ ^ each edge e = {u, v } in G might have a corresponding edge ^ e = {u, v } in G, in which case we call e an actual edge ^ ^^ and call e the image of e, or might not have a corresponding ^ ^ edge in G, in which case we call e a virtual edge. In the second case, the edge e is added via a clique-sum decomposition when completing the join set. We start by "dealing with vortices" in such a way that we can omit them in the rest of the proof: L E M M A 7 . 1 . Suppose G is a h-almost embeddable graph ^ in a clique-sum decomposition of a graph G. Let G be the graph obtained by contracting all regions containing a vortex. Then graph G has linear local treewidth if and only if G has linear local treewidth. Proof. As mentioned before, all edges of a face containing a vortex of G are actual edges. Now suppose G = G0  G1  · · ·  Gh  X is almost-embedded in a surface  of genus g . Suppose Ui (as defined in Definition 2.2) is {ui [1], ui [2], . . . , ui [mi ]}. Let G0 be the graph obtained from G0 by adding new vertices c1 , c2 , . . . , ch , placing ci inside the region of G0 in which Gi is placed, and adding edges {ci , ui [j ]} and {ui [j ], ui [j + 1]} (where j + 1 is treated modulo mi ) for all 1  i  h and 1  j  mi . By adding these edges, the vertices Ui , 1  i  h, form a cycle in G0 . In addition, for each apex x  X , we add an edge {x, ci } to G0 if and only if there is an edge {x, v } in G for some v  Gi , for all i. Using an argument similar to Grohe's argument [17] (in the proof of Theorem 6.1), we can show that if G0 has linear local treewidth ar + b, then G also has local treewidth at most (h2 + 1)ar + (h2 + 1)b + O(h), which is linear in terms of r. (One difference is that, in Grohe's proof, there are no apices; however, by including all apices in all bags, we increase the treewidth by at most O(h), and proximity is preserved because of the edges {x, ci }.) Next we construct graph G0 from G0 by subdividing each ui [j ]. More precisely, we obtain graph G0 from G0 by adding new vertices ci for 1  i  h (again placed in the region of G0 corresponding to Gi ), vertices ui [j ] and ui [j ] for 1  i  h and 1  j  mi , and edges {ci , ui [j ]}, {ui [j ], ui [j + 1]}, and {ui [j ], ui [j ]} (where j + 1 is treated modulo mi ) for all 1  i  h and 1  j  mi . In addition, for each apex x  X , we add an edge {x, ci } to G0 if and only if there is an edge {x, v } in G for some v  Gi . We can see that G0 has linear local treewidth if and only if G0 has linear local treewidth. More precisely, 0 0 G0 1 (r)  ltwG (r)  ltwG (2r). Here the factor of 2 2 ltw in the right-hand side appears because each edge in G0 is at
1 For ease of notation, this section uses G to denote a piece of the graph ^ instead of the original graph, denoted by G in this section.

845


most split in two in G0 . The factor of 1 in the left-hand side 2 appears because the treewidth of each neighborhood in G0 grows by at most a factor of 2 with respect to the treewidth of the corresponding neighborhood in G0 (because we can replace each vertex ui [j ] in a bag of a tree decomposition in G0 by both vertices ui [j ] and ui [j ] in the corresponding bag of the tree decomposition in G0 ). Finally, we obtain graph G0 from G0 with the following transformation. First, we delete any edges {ci , x} for each x  X . By Corollary 6.1, this operation preserves linear local treewidth, because there are at most h2 such edges. Then we delete ci and contract the face formed by vertices that used to be adjacent to ci into a new vertex ci , for all 1  i  h. By Lemma 6.3 and because we preserve proximity, this operation preserves linear local treewidth. Finally, we delete ci and contract the face formed by vertices that used to be adjacent to ci , which is the same as the original face of G0 in which Gi was placed. For the same reason, this operation preserves linear local treewidth and proximity. The resulting graph G0 is the G desired by the lemma. 2 Because we would like the piece G to be apex-minor^ free like G, we need to be able to obtain virtual edges via contractions. First we mention some basic (but usually hidden) information about virtual edges and where they arise in Theorem 2.1. The proof of Theorem 2.1 by Robertson and Seymour [32] shows that, in fact, the join set of each clique-sum contains at most three vertices of the piece that are neither apices nor vortices. In the next step we deal with virtual edges. Intuitively, for each piece G in the clique-sum decomposition of the ^ original graph G, we construct a graph G which is a minor ^ and "approximately" preserves the virtual edges of each of G piece in the following sense: D E FI N I T I O N 7 . 1 . Let G be a h-almost-embeddable graph in ^ a clique-sum decomposition of a graph G. The approxima~ tion graph of G, denoted by G, can be obtained as follows. First we perform the reduction described in Lemma 7.1, i.e., contract each vortex and its corresponding face into a single vertex. Next we remove the virtual edges from the graph and replace some of them as follows. For each clique-sum of G with a graph G via a join set W , where |W  (V (G) - X )| > 1, we do the following: 1. If |W  (V (G) - X )| = 2, we add edges from all vertices of W to an arbitrary vertex in W  (V (G) - X ) (located on the surface). 2. If |W  (V (G) - X )| = 3 and there is more than one clique-sum that contains W  (V (G) - X ) in its join set, we add all edges among W  (V (G) - X ) and then add edges from all vertices in W - (V (G) - X ) to a vertex in W  (V (G) - X ). For each different clique-sum, we choose a different vertex in W  (V (G) - X ), as long as we can avoid repetition. 3. If |W  (V (G) - X )| = 3 and there is only one clique-

sum that contains W (V (G)-X ) in its join set, we add a new vertex v inside the triangle of W  (V (G) - X ) on the surface and then add all edges from all vertices of W to v . L E M M A 7 . 2 . Let G be a h-almost-embeddable graph in a ^ clique-sum decomposition of a graph G. The approximation ~ ^ graph G is a minor of G. L E M M A 7 . 3 . Let G be an h-almost-embeddable graph in a ^ clique-sum decomposition of a graph G. The approximation ~ has linear local treewidth if and only if G has linear graph G local treewidth. To encourage reader, we point out that we are making progress. By construction, the approximation graph no longer contains vortices. Furthermore, by Lemmas 7.2 and 7.3, the approximation graph has linear local treewidth if (and only if) the piece G in the clique-sum decomposition ^ of G has linear local treewidth, and simultaneously the ^ approximation graph is a minor of the original graph G. ~ In the rest of the proof, we show that each apex of G can be connected to only a bounded number of "local areas of planarity" which can be attached to the graph via clique-sums and themselves have linear local treewidth. To find such local areas, we first need to make sure that the representativity of ~ the bounded-genus graph G - X is relatively high, or it is embedded on a sphere. In the rest of the proof, because the ~ approximation graph G approximates the properties we need ~ from the piece G, we use G and G interchangeably. L E M M A 7 . 4 . Let G be a graph and X  V (G) is a set of its apices where |X |  h, such that G - X is 2-cell embedded in a surface  of genus g . We have one of the following cases: 1.  is a sphere, i.e. g = 0; 2. Representativity of G is at least N1 (a positive constant to be determined later); c 3. G has a set X of size at most h + N1 such that G - X an be 2-cell embedded in a surface with genus strictly smaller than g ; and 4. G = G1  G2  · · ·  Gk such that X  V (Gi ) for all i, 1  i  k , and Gi - X can be 2-cell embedded in a surface with genus strictly smaller than g . By applying Lemma 7.4 any bounded number of times to ~ ~ the graph G, we can obtain a clique-sum decomposition G = ~ 1  G2  · · ·  Gk such that each graph Gi has a bounded ~ ~ ~ G ~ ~ ~ number of apices Xi and each Gi - Xi is either a planar graph or a graph with representativity at least some constant lower bound. In fact, the representativity lower bound that we will need in Lemma 7.7 is not a fixed quantity, and indeed ~ is different for each term Gi . Specifically, the lower bound ~ ~ ~ is lhi N2 which depends on the number of apices hi = |Xi | ~ in each term Gi , the degree l of the apex in the apex graph H , and the constant N2 (determined in the next lemma).

846


To achieve this lower bound, we apply Lemma 7.4 to each ~ term Gi that does not have sufficiently high representativity, unless the term is already planar. Note that, as we recurse, ~ we increase the values of hi for some i and therefore require a stronger lower bound on the representativity of those terms. ~ Because hi increases by only a constant, and because the maximum depth of recursion is bounded by g , the final values ~ of hi are bounded, so the lower bound on representativity is also bounded. Using Lemma 7.4 and Theorem 4.2, we only need to ~ show that each resulting term Gi , 1  i  k , has linear local treewidth. We divide this claim into two cases: (1) where ~ ~ Gi - Xi has sufficiently high representativity, and (2) where ~ ~ Gi - Xi is planar. The next few lemmas deal with the first case. First, we determine the necessary value of N2 :

Now, we consider the structure of each of boundedradius disks. ~ L E M M A 7 . 8 . Let C be a bounded radius disk in Gi . More precisely, C contains all vertices and regions of distance at most r from the center c  V (G), where the distance is with ~ ~ respect to the metric of the tangle of Gi - Xi mentioned in Lemma 7.5. Then we can write C as ( N1 )-sums of a graph of pathwidth at most N2 and several planar graphs each with a bounded number of apices. ~ Lemma 7.8 also applies if we consider the apices of Gi , because we can easily add all apices to all planar graphs. If we also apply Lemma 7.8 once for each disk in the disjoint disk covering, then we arrive at the following:

~ C O RO L L A RY 7 . 1 . Each graph Gi can be written as P0  P1  · · · Pk where P0 is a bounded-genus graph with a L E M M A 7 . 5 . For any apex graph H , there is an integer bounded number of vortices and apices such that each apex N2  0 with the following property. Let G be a minor of is attached only to vortices, and each P , 1  i  k , is a i G such that G - X can be 2-cell embedded in a surface  of planar graph with a bounded number of apices. In addition, - genus g , and let T be a tangle of G X with metric d. Also if we remove all edges between pairs of apices, the rest of the assume that the representativity of G - X is at least N2 . graph is a minor of G and G. ~i ^ Then, for each vertex x  X , if x is adjacent to v1 , . . . , vl where l is the degree of the apex in H , and d(vi , vj )  N2 At first glance, it may seem that we have arrived for all 1  i = j  l, then G has a minor isomorphic to H . to our initial state before Lemma 7.1: again we have a bounded-genus graph plus apices and vortices. However, we Proof. The proof is very similar to the proof of [26, Sec- have made substantial progress because now in this almosttion 9], [30, Theorems 4.4 and 4.5], or [23, Theorem 2.2], embeddable graph P0 all apices are attached only to vortices. and we omit the details. 2 Using a proof similar to the proof of Lemma 7.1, now we are able to remove apices and vortices from P0 without destroyUsing Lemma 7.5, we go one step towards finding the ing the linear local treewidth property. As a result, we convert local areas of planarity as follows. Roughly, the following P into a bounded-genus graph without apices and vortices, 0 ~ lemma says that the neighborhood of an apex in Xi in the and Eppstein [15] proved that such graphs have linear local ~ ~ bounded-genus graph Gi - Xi can be covered by a bounded treewidth. number of bounded-radius disks, where the disks are defined To finish the high-representativity case, it remains only ~ ~ by the metric d of the tangle Gi - Xi . to show that each Pi , 1  i  k , has linear local treewidth. L E M M A 7 . 6 . Let l be the degree of the apex in apex graph In fact, each Pi is a planar graph plus apices, making them ~ ~ ~ ^ H which is excluded by the original graph G, and let d be equivalent to the other case of Gi 's in which Gi - Xi is ~ ~ the metric of the tangle of Gi - Xi mentioned in Lemma 7.5. planar. Therefore, we can finish all remaining loose ends ~ ~ Then, for each vertex x in the set Xi of apices of Gi , there is with a final lemma: ~ i ) - Xi ) such ~ a set Ci of at most l centers (vertices of V (G ~ i - Xi , there is a center c L E M M A 7 . 9 . If a graph G has a subset X of vertices of size ~ that, for each neighbor u of x in G at most a constant h such that (1) if we remove edges between in Ci such that d(c, u)  N2 . pairs of vertices in X , G becomes H -minor-free where H is We now combine this disk cover over all apices, and an apex graph, and (2) G - X is a planar graph, then G has make the cover disjoint, to obtain our desired local areas of linear local treewidth. planarity as follows. Proof. First, we can assume that all edges among vertices L E M M A 7 . 7 . Let l be the degree of the apex in apex graph in X exist in graph G, because if we add all such edges, the ^ H which is excluded by the original graph G, let d be the new graph has linear local treewidth if and only if the original ~ ~ metric of the tangle of Gi - Xi mentioned in Lemma 7.5, and graph has linear local treewidth by Corollary 6.1 and because ~ ~ ~ ~ let hi = |Xi |. Suppose that the representativity of Gi - Xi is |X |  h. G ~ ~ at least lhi N2 . Then there is a set Ci of at most lhi vertices We claim that it suffices to show that tw(G[Nr (X )])  ~ ~ ~ such that, for each neighbor u of any x  Xi in Gi - Xi , cr + d for some constants c and d. Suppose we had this G G ~ there is exactly one center c in Ci for which d(c, u)  lhi N2 . relation. Because Nr (v )  Nr (X ) for each v  X ,

847


G G we have tw(G[Nr (v )])  tw(G[Nr (X )])  cr + d for G each v  X . For each v  V (G) - X , if Nr (v )  X = , G then because G is a planar graph, we have tw(G[Nr (v )])  3r - 1 which is linear. On the other hand, if v  V (G) - X G G and there exists an x  Nr (v )  X , then we have Nr (v )  G G G N2r (x) and thus tw(G[Nr (v )])  tw(G[N2r (X )])  2cr + d as desired. G To show that tw(G[Nr (X )])  cr + d, we consider a G fixed r and let w = tw(G[Nr (X )]). We know that w - h  G G tw(G[Nr (X )] - X )  w, so tw(G[Nr (X )] - X ) = (w). G Because the planar graph G[Nr (X )] - X has treewidth at least (w), by [24, Theorem 6.2], it has a ((w) × (w))grid as a minor. If, during the course of taking a minor to obtain such a grid, we apply only contractions and ignore deletions, then we obtain a partially triangulated ((w) × (w)) grid R. Next we consider the tangle of the grid R and its corresponding metric. Let x be a vertex in X and let N (x) be the neighbors of x in R (i.e., we consider the neighbors of x after the contractions). By the theory of Robertson and Seymour (see [26, Section 9] or [30, Theorems 4.4 and 4.5]), if we have n vertices of an (r × r)-grid such that each pair has distance at least some constant N2 and each vertex has distance at least N2 from the boundary of the outer region, then by taking a minor of the (r × r)-grid we can construct any planar graph whose vertex set is precisely these n vertices. (In fact, this theorem uses the distance metric of the tangle, but for triangulated grids, this distance is proportional to the normal graph distance.) Because G without edges among X is H -minor-free and H is an apex graph, n cannot be more than |V (H )| - 1. In other words, for each vertex x  X , there is a set Cx  N (x) of at most h1 = |V (H )| - 1 vertices (centers) such that the distance in R between any pair of vertices in Cx is at least N2 , and every vertex of N (x) in the central ((w) - 2N2 × (w) - 2N2 )grid R of R has distance at most N2 from one of the vertices of Cx . Consider the set of disks with centers from Cx over all apices x  X , all with radius N2 . By "merging" overlapping disks as in Lemma 7.7, we obtain a bounded number of disjoint disks with bounded radius. We perform the following modifications to the planar graph G - X . For every two adjacent rows that intersect a disk, we contract vertically into a single row, and then remove edges to avoid multi-edges and loops. (These edge removals are valid because they do not affect distances.) Similarly, we contract adjacent columns that intersect disks. We also contract the N2 outermost rings of the grid down to a single ring (again removing edges to avoid multi-edges and loops). Finally, we add edges to connect one vertex v on the new outermost ring to every other vertex on the outermost ring, and add v to the set of centers. The resulting graph R is still planar; indeed, it is a partially triangulated ((w) × (w))grid, and thus its treewidth is still (w). Furthermore, each

disk has been contracted down to a single vertex, which we can think of as the center. Because every vertex in the original grid R has distance h at most r from an apex, every vertex in the new grid R as distance at most r from a center. By Corollary 6.2, the treewidth is linear in r, and therefore (w) = (r). 2 ~ Thus by Lemma 7.9 we conclude that each term Gi and ~ and G itself (by Lemma 7.3) thus the approximation graph G ^ have linear local treewidth. Because the original graph G can be written as a clique-sum of such graphs of linear local ^ treewidth, by Lemma 4.2, the apex-minor-free graph G has linear local treewidth. 8 Conclusions and Future Work In this paper, by reproving the main theorem of Eppstein [15] using the deep Graph Minor Theory of Robertson and Seymour, we showed that the concept of local treewidth and linear local treewidth are the same for minor-closed families of graphs. Using this result, we obtain PTASs with approximation ratio 1 +  running in 2O(1/) nO(1) time (instead nO(1) time) for many NP-complete problems on of 22 minor-closed classes of graphs with bounded local treewidth. The constants that we obtain for linear local treewidth of apex-minor-free graphs are not the best. It would be interesting to improve these constants, even for special class of graphs (see e.g. Demaine et al. [11], Grohe [17], or Eppstein [17]), because of the direct improvement on the exponents in the running time of (and thus the practicality of) PTASs for many NP-complete problems on these graphs. We re-enforce another open problem posed by Eppstein [15] which asks whether there are natural nontrivial families of graphs which are not minor-closed but that have bounded local treewidth. (A trivial example is bounded-degree graphs, or other classes in which a bound on diameter imposes a limit on total graph size.) Given our results, a natural question is whether there are any (non-minor-closed) families of graphs that have bounded local treewidth but not linear local treewidth. Recently, several papers have been published on exponential speedup of fixed parameter algorithms on special class of graphs; see e.g. [1, 9, 13]. Most of these results bound the treewidth of the graph as a linear function in the square-root of the size of a minimum dominating set. One can easily observe that there is no such bound for general apex graphs, and therefore the most general minor-closed families of graphs to which we could hope to obtain such a relation are apex-minor-free graphs. By following through our series of reductions, we obtain that indeed apex-minorfree graphs have such a relation. In fact, we conjecture that any apex-minor-free graph can be represented as a cliquesum of almost-embeddable graphs such that, in each piece, an apex is attached only to vortices. This conjectured characterization of apex-minor-free graphs whose proof we believe that follows our approach would easily lead to our linear local
2O (1/)

848


treewidth bound and the aforementioned bound on treewidth with respect to dominating set.
Acknowledgments. The authors are indebted to Paul D. Seymour for many important discussions that led to the proof of the main combinatorial result of this paper (Theorem 4.3) and for providing a portal into the Graph Minor Theory and revealing some of its hidden structure that we use in this proof. We also thank Fedor Fomin, Naomi Nishimura, Prabhakar Ragde, and Dimitrios Thilikos for encouragement and helpful discussions.

References
[1] J . A L B E R , H . L . B O D L A E N D E R , H . F E R NAU , A N D R . N I E D E R M E I E R , Fixed parameter algorithms for planar dominating set and related problems, in Algorithm theory-- Scandinavian Workshop on Algorithm Theory 2000 (Bergen, 2000), Springer, Berlin, 2000, pp. 97­110. [2] N . A L O N , P. S E Y M O U R , A N D R . T H O M A S, A separator theorem for graphs with excluded minor and its applications, in Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (Baltimore, 1990), 1990, pp. 293­299. [3] S . A R N B O R G A N D A . P RO S K U ROW S K I, Linear time algorithms for NP-hard problems restricted to partial k-trees, Discrete Appl. Math., 23 (1989), pp. 11­24. [4] B . S . BA K E R, Approximation algorithms for NP-complete problems on planar graphs, J. Assoc. Comput. Mach., 41 (1994), pp. 153­180. [5] M . C H A R I K A R A N D A . S A H A I, Dimension reduction in the l1 norm, in The 43th Annual Symposium on Foundations of Computer Science (FOCS'02), 2002, pp. 551­560. [6] C . C H E K U R I , A . G U P TA , I . N E W M A N , Y. R A B I N OV I C H , A N D S . A L I S TA I R , Embedding k -outerplanar graphs into 1, in ACM-SIAM Symposium on Discrete Algorithms (SODA'03), 2003, pp. 527 ­ 536. [7] Z . - Z . C H E N, Efficient approximation schemes for maximization problems on K3,3 -free or K5 -free graphs, J. Algorithms, 26 (1998), pp. 166­187. [8] N . C H I BA , T. N I S H I Z E K I , A N D N . S A I T O, An approximation algorithm for the maximum independent set problem on planar graphs, SIAM J. Comput., 11 (1982), pp. 663­675. [9] E . D . D E M A I N E , F. V. F O M I N , M . H A J I AG H AY I , A N D D . M . T H I L I KO S, Fixed-parameter algorithms for the (k, r)center in planar graphs and map graphs, in The 30th International Colloquium on Automata, Languages and Programming (ICALP 2003), 2003. To appear. [10] E . D . D E M A I N E A N D M . H A J I AG H AY I, Equivalence of local treewidth and linear local treewidth and its algorithmic applications, Tech. Rep. MIT-LCS-TR-903, M.I.T, May 2003. [11] E . D . D E M A I N E , M . H A J I AG H AY I , N . N I S H I M U R A , P. R AG D E , A N D D . M . T H I L I KO S, Approximation algorithms for classes of graphs excluding single-crossing graphs as minors. To appear in Journal of Computer and System Sciences. [12] E . D . D E M A I N E , M . H A J I AG H AY I , A N D D . M . T H I L I KO S, A 1.5-approximation for treewidth of graphs excluding a graph with one crossing, in The 5th International Workshop on Approximation Algorithms for Combinatorial Optimization (Italy, APPROX 2002), LNCS, 2002, pp. 67­80. [13] , Exponential speedup of fixed parameter algorithms on K3,3 -minor-free or K5 -minor-free graphs, in The 13th Annual International Symposium on Algorithms and Computation (Vancouver, ISAAC 2002), 2002, pp. 262­273.

[14] D . E P P S T E I N, Subgraph isomorphism in planar graphs and related problems, in Proceedings of the Sixth Annual ACMSIAM Symposium on Discrete Algorithms (San Francisco, CA, 1995), New York, 1995, ACM, pp. 632­640. [15] , Diameter and treewidth in minor-closed graph families, Algorithmica, 27 (2000), pp. 275­291. [16] M . F R I C K A N D M . G RO H E, Deciding first-order properties of locally tree-decomposable graphs, J. ACM, 48 (2001), pp. 1184­1206. [17] M . G RO H E, Local tree-width, excluded minors, and approximation algorithms. To appear in Combinatorica. [18] A . G U P TA , I . N E W M A N , Y. R A B I N OV I C H , A N D S . A L I S TA I R , Cuts, trees and l1 -embeddings of graphs, in The 40th Annual Symposium on Foundations of Computer Science (FOCS'99), 1999, pp. 399­409. [19] M . H A J I AG H AY I , N . N I S H I M U R A , P. R AG D E , A N D D . M . T H I L I KO S, Fast approximation schemes for K3,3 -minor-free or K5 -minor-free graphs, in Euroconference on Combinatorics, Graph Theory and Applications 2001 (Barcelona, 2001), 2001. [20] P. N . K L E I N , S . A . P L OT K I N , A N D S . R AO, Excluded minors, network decomposition, and multicommodity flow, in The Twenty-Fifth Annual ACM Symposium on Theory of Computing (STOC'93), 1993, pp. 682­690. [21] R . J . L I P T O N A N D R . E . TA R JA N, Applications of a planar separator theorem, SIAM J. Comput., 9 (1980), pp. 615­627. [22] S . A . P L OT K I N , S . R AO , A N D W. D . S M I T H, Shallow excluded minors and improved graph decompositions, in The Fifth Annual ACM-SIAM Symposium on Discrete Algorithms(SODA'94), 1994, pp. 462­470. [23] N . RO B E RT S O N A N D P. S E Y M O U R, Excluding a graph with one crossing, in Graph structure theory (Seattle, WA, 1991), Amer. Math. Soc., Providence, RI, 1993, pp. 669­675. [24] N . RO B E RT S O N , P. S E Y M O U R , A N D R . T H O M A S, Quickly excluding a planar graph, J. Combin. Theory Ser. B, 62 (1994), pp. 323­348. [25] N . RO B E RT S O N A N D P. D . S E Y M O U R, Graph minors. II. Algorithmic aspects of tree-width, J. Algorithms, 7 (1986), pp. 309­322. [26] N . RO B E RT S O N A N D P. D . S E Y M O U R, Graph minors. VII. Disjoint paths on a surface, J. Combin. Theory Ser. B, 45 (1988), pp. 212­254. [27] , Graph minors. X. Obstructions to tree-decomposition, J. Combin. Theory Ser. B, 52 (1991), pp. 153­190. [28] , Graph minors. XI. Circuits on a surface, J. Combin. Theory Ser. B, 60 (1994), pp. 72­106. [29] , Graph minors. XII. Distance on a surface, J. Combin. Theory Ser. B, 64 (1995), pp. 240­272. [30] , Graph minors. XII. Distance on a surface, J. Combin. Theory Ser. B, 64 (1995), pp. 240­272. [31] , Graph minors. XVII. Taming a vortex, J. Combin. Theory Ser. B, 77 (1999), pp. 162­210. [32] N . RO B E RT S O N A N D P. D . S E Y M O U R, Graph minors XVI. excluding a non-planar graph, (2003). To appear in J. Combin. Theory Ser. B, available electronically in journal site. [33] M . YA N NA K A K I S, Node- and edge-deletion NP-complete problems, in Conference Record of the Tenth Annual ACM Symposium on Theory of Computing (San Diego, CA, 1978), ACM press, New York, 1978, pp. 253­264.

849