Fixed-Parameter Algorithms, IA166 Sebastian Ordyniak Faculty of Informatics Masaryk University Brno Spring Semester 2013 Planar Graphs Introduction Outline 1 Planar Graphs Introduction Algorithms on Planar Graphs Locally Bounded Treewidth Layer decompositions and Applications Bidimensionality and Applications Planar Graphs Introduction Planar Graphs Planar Graphs Introduction Definitions and Basic Facts Let G be a graph. A drawing of G in the plane R2 is a mapping Π that maps all vertices v ∈ V(G) to distinct points Π(v) in R2, and edges {u, v} ∈ E(G) to simple curces between Π(u) and Π(v). A planar embedding of G is a drawing of G without edge crossings, i.e., the curces corresponding to the 2 edges can only have a common endpoints of the edges in common. A plane graph (G, Π) consists of G and a planar embedding Π of G. G is planar if it admits a planar embedding. Planar Graphs Introduction Definitions and Basic Facts Let G be a graph. Let Π be a planar embedding of G. The faces of Π are the maximal connected subsets of R2 that contain no images of Π, i.e., the regions of R2 \ Π(V ∪ E). A plane graph has 1 unbounded face. This is called the outer face. Proposition Let (G, Π) be a connected plane graph such that every edge lies on a cycle of G. Then the boundaries of faces are (images of) cycles, and (the image of) every edge is contained in the boundary of two faces. Planar Graphs Introduction Definitions and Basic Facts Let G be a graph. Euler’s formula Let (G, Π) be a non-empty connected plane graph with n vertices, m edges and f faces. Then n − m + f = 2. Planar Graphs Introduction Definitions and Basic Facts Let (G, Π) be a plane graph. A triangulation of (G, Π) is a plane graph (G , Π ) with V(G) = V(G ), E(G) ⊆ E(G ), and Π extends Π such that G is connected and every edge of G lies on a cycle, and all faces of (G , Π ) are triangles. Proposition If |V(G)| ≥ 3, a triangulation of (G, Π) exists and can be constructed in time O(|E(G)|). Planar Graphs Introduction Definitions and Basic Facts Proposition Let G be a planar graph with |V(G)| ≥ 3. Then |E(G)| ≤ 3|V(G)| − 6. Proof: Let n := |V(G)| and m = |E(G)|. Let Π be a planar embedding of G with f faces. By the previous proposition it suffices to show the statement in case (G, Π) is a triangulation. In this case all faces are triangles and every edge is part of 2 faces, hence 3f = 2m. Then Euler’s formula gives m = n + f − 2 = n + 2 3 m − 2 and m = 3n − 6. Planar Graphs Introduction Definitions and Basic Facts Corollary Every planar graph has a vertex of degree at most 5. Theorem In linear time it can be checked whether a given graph is planar and if so a planar embedding can be computed. Four Color Theorem Every planar graph admits a proper 4-vertex coloring. Planar Graphs Algorithms on Planar Graphs Outline 1 Planar Graphs Introduction Algorithms on Planar Graphs Locally Bounded Treewidth Layer decompositions and Applications Bidimensionality and Applications Planar Graphs Algorithms on Planar Graphs k-PLANAR INDEPENDET SET k-PLANAR INDEPENDET SET Parameter: k Input: A planar graph G and an integer k. Question: Does G have an independent set of size at least k? For the non-planar version of the problem, FPT algorithms are unlikely to exists (W[1]-hard), but for the planar version FPT algorithms are easily found. Planar Graphs Algorithms on Planar Graphs k-PLANAR INDEPENDET SET Trivial FPT algorithms for k-PLANAR INDEPENDENT SET: Kernelization Because of the Four Color Theorem G is 4-colorable. Hence, G has an independent set of size at least |V(G)|/4. Hence, without any preprocessing, a 4k-vertex kernel is obtained, which is actually also a 4k-edge kernel because |E(G)| ≤ 3|V(G)| − 6. Planar Graphs Algorithms on Planar Graphs k-PLANAR INDEPENDET SET Trivial FPT algorithms for k-PLANAR INDEPENDENT SET: Branching Consider a vertex v of degree at most 5. A maximal independent set contains v or 1 of its neighbors. Branching on this choice yields a search tree with at most 6k leaves. Planar Graphs Algorithms on Planar Graphs Treewidth of Planar Graphs Some Definitions: The length of a (v1, vk )-path v1, . . . , vk is k − 1, and the distance between 2 vertices u and v is the minimum length over all (u, v)-paths, or ∞ is no such path exists. The diameter of a graph is the maximum distance between any two vertices. The height of a rooted tree is the maximum distance from the root to a leaf. Planar Graphs Algorithms on Planar Graphs Treewidth of Planar Graphs Theorem Let G be a planar graph for which a rooted spanning tree T of height l is given. Then a tree decomposition of G of width at most 3l exists, and can be constructed in polynomial time. Corollary A planar graph with diameter D has a tree decomposition of width at most 3D. Proof: Construct a breadth-first search tree starting at arbitrary root vertex. Planar Graphs Algorithms on Planar Graphs Treewidth of Planar Graphs Theorem Let G be a planar graph for which a rooted spanning tree T of height l is given. Then a tree decomposition of G of width at most 3l exists, and can be constructed in polynomial time. Proof: Let (G, Π) be a planar embedding of G and T be the spanning tree of height l with root r. W.l.o.g. we can assume that G is triangulated. We may assume that |V(G)| ≥ 4 (the case |V(G)| ≤ 3 is trivial). Hence, 2 faces share at most 1 edge. Planar Graphs Algorithms on Planar Graphs Treewidth of Planar Graphs Proof, continued: Let F be the set of faces of (G, Π). Let T∗ be the graph with vertex set V(T∗) := F and {f, g} ∈ E(T∗) iff the boundaries of the faces f and g share an edge in E(G) \ E(T). For f ∈ F, define the bag Xf to contain the 3 vertices u, v, w on the boundary of f, and all of their ancestors with respect to T and r. We will prove that (T∗, X) is the desired tree decomposition of G. Lemma (T∗, X) is a tree decomposition of G of width at most 3l. Planar Graphs Algorithms on Planar Graphs Treewidth of Planar Graphs Claim T∗ contains no cycles. Proof: A cyle C := f0, . . . , fk , f0 of T∗ corresponds to a simple closed curve C in the plane through the faces f1, . . . , fk that crosses the edge shared by fi and fi+1 mod k exactly once for all i and crosses no other edges. By the Jordan Curve Theorem C divides the plane into 2 regions, which both contain at least 1 vertex. Because C crosses no edges of T, this contradicts that T is a spanning tree. Planar Graphs Algorithms on Planar Graphs Treewidth of Planar Graphs Claim For every face f, |Xf | ≤ 3l + 1. Proof: Xf contains the 3 vertices on its boundary and all of its ancestors in T. Because T has height l, every vertex has at most l ancestors. The root r is shared a shared ancestor of the 3 vertices. Hence, |Xf | ≤ 3 + 3l − 2 = 3l + 1. Planar Graphs Algorithms on Planar Graphs Treewidth of Planar Graphs Claim For every edge {u, v} ∈ E(G) there is an f ∈ V(T∗) with {u, v} ∈ Xf . Proof: This is trivial because every edge lies on the boundary of at leasy one face. Planar Graphs Algorithms on Planar Graphs Treewidth of Planar Graphs Claim For every v ∈ V(G), the subgraph of T∗ induced by X−1(v) is non-empty and connected. Proof: By induction over the height of the subtree rooted at v. Induction Start: If v is a leaf of T, then v ∈ Xf iff v is incident with f. Because v is a leaf, the faces incident with v induce a path in T∗. Induction Step: Suppose v is not a leaf and v = r. Let v0, . . . , vd−1 be the neighbors of v in clockwise order around v such that v0 is the parent of v in T. Let f0, . . . , fd−1 be the faces incident with v such that fi is incident with vi and vi+1 mod d . Planar Graphs Algorithms on Planar Graphs Treewidth of Planar Graphs Proof, continued: Let f0, . . . , fd−1 be the faces incident with v such that fi is incident with vi and vi+1 mod d . Let vi1 , . . . , vik be the children of v in T. Then v is contained in all bags Xfi and in all bags that also contain a child vij , but in no other bags, i.e.: X−1(v) = {f0, . . . , fd−1} ∪ X−1(vi1 ) ∪ · · · ∪ X−1(vik ) By induction X−1(vij ) is connected for every j. If the edge shared by fi and fi+1 is not in T, then they are adjactent in T∗. Otherwise, they share an edge {v, vij }, and are both part of the connected set X−1(vij ). This shows that X−1(v) is connected in T∗. If v is the root of T the argument is similar. Planar Graphs Algorithms on Planar Graphs Treewidth of Planar Graphs Because the root r is part of every bag Xf and X−1(r) induces a connected subgraph of T∗ by the previous claim it follows that T∗ is also connected. Summary: T∗ contains no cycles and is connected. For every f, |Xf | ≤ 3l + 1. Every edge {u, v} ∈ E(G) is covered by some Xf . For every v ∈ V(G) the subgraph of T∗ induced by X−1(v) is connected. Hence, (T∗, X) is the desired tree decomposition of G. Planar Graphs Algorithms on Planar Graphs k-PLANAR DOMINATING SET k-PLANAR DOMINATING SET Parameter: k Input: A planar graph G and an integer k. Question: Does G have a dominating set S of cardinality at most k? Theorem k-PLANAR DOMINATING SET is fixed parameter tractable. Planar Graphs Algorithms on Planar Graphs k-PLANAR DOMINATING SET Theorem k-PLANAR DOMINATING SET is fixed parameter tractable. Proof: W.l.o.g. we can assume that G is connected. Compute the diameter d of G in polynomial time (e.g. using BFS trees). If d ≥ 3k then return NO. This is correct because a vertex can dominate at most 3 vertices of any shortest path. Otherwise, planarly embed the graph, construct a BFS tree of height at most 3k − 1, and use it to construct a tree decomposition of width at most 3(3k − 1) (all can be done in polynomial time). Use dynamic programming to find the correct answer. Planar Graphs Algorithms on Planar Graphs Summary and Outlook When restricted to planar graphs, FPT algorithms exist for problems that are unlikely to admit FPT algorithms for general graphs (e.g. k-INDEPENDENT SET and k-DOMINATING SET). One essential property for this is that for planar graphs, the treewidth is bounded by a function of the diameter (they have bounded local treewidth). There are many more graph classes with bounded local treewidth, and this can be used to construct FPT algorithms for them. Planar Graphs Locally Bounded Treewidth Outline 1 Planar Graphs Introduction Algorithms on Planar Graphs Locally Bounded Treewidth Layer decompositions and Applications Bidimensionality and Applications Planar Graphs Locally Bounded Treewidth Locally Bounded Treewidth Definition Let C be a class of graphs. C has locally bounded treewidth if there is a function f : N → N such that for every G ∈ C, v ∈ V(G), and natural number r it holds that tw(G[NG r [v]]) ≤ f(r). Every class of graphs of bounded treewidth also has locally bounded treewidth. We have already seen that planar graphs have locally bounded treewidth. There are many more important graph classes that have locally bounded treewidth such as graph classes of bounded degree, graph classes of bounded genus, etc.. Planar Graphs Locally Bounded Treewidth A Meta-Theorem for FO-Logic and Locally Bounded Treewidth Theorem Let C be a class of graphs with locally bounded treewidth and Φ be an FO-formula of length k. Then it can be decided in time f(k)O(n2) whether G |= Φ for every G ∈ C. FO-definable problems include problems such as k-DOMINATING SET and k-INDEPENDENT SET it does not include MSO-definable problems such as COLORING and HAMILTONICITY, etc. Planar Graphs Locally Bounded Treewidth A Meta-Theorem for FO-Logic and Locally Bounded Treewidth To sketch a proof of the Meta-Theorem we need the following Notions and Facts: Let r be a natural number. We denote by d(x, y) > r the FO-formula such that G |= d(v, u) > r iff the vertices v and u have distance at least r in G. We say a FO-formula Φ(x) is r-local iff the validity of Φ(x) only depends on the r-neighborhood of x, i.e., if for all graphs G and vertices v ∈ V(G) it holds that G |= Φ(v) iff G[NG r [v]] |= Φ(v). Planar Graphs Locally Bounded Treewidth A Meta-Theorem for FO-Logic and Locally Bounded Treewidth Gaifman’s Theorem Every FO-sentence is equivalent to a Boolean combination of sentences of the form: ∃x1, . . . xl( 1≤i 2r ∧ 1≤i≤l Φ(xi) with l, r ≥ 1 and r-local Φ(x). Furthermore, such a boolean combination can be found in an effective way. The above theorem is sometimes also called the Locality Theorem for FO-Logic. Planar Graphs Locally Bounded Treewidth A Meta-Theorem for FO-Logic and Locally Bounded Treewidth Let G be a graph, S ⊆ V(G) and l, r ∈ N. Then S is (l, r)-scattered if there exist v1, . . . , vl ∈ S such that dG(vi, vj) > r for every 1 ≤ i < j ≤ l. Lemma Let C be a class of graphs of locally bounded treewidth. Then there is an algorithm that, given G ∈ C, a set S ⊆ V(G) and l, r ∈ N, decides if S is (l, r)-scattered in time g(l, r)|V(G)|. Planar Graphs Locally Bounded Treewidth A Meta-Theorem for FO-Logic and Locally Bounded Treewidth Lemma Let C be a class of graphs of locally bounded treewidth. Then there is an algorithm that, given G ∈ C, a set S ⊆ V(G) and l, r ∈ N, decides if S is (l, r)-scattered in time g(l, r)|V(G)|. Proof: We start by computing a maximal set T ⊆ S such dG(ti, tj) > r for every 1 ≤ i < j ≤ |T|. Clearly, such a set T can be easily found by a simple greedy algorithm. If |T| ≥ l then we are done. So suppose |T| < l. Because of the maximality of T it holds that S ⊆ NG r [T] and S is (l, r)-scattered in G iff S is (l, r)-scattered in NG 2r [T]. Planar Graphs Locally Bounded Treewidth A Meta-Theorem for FO-Logic and Locally Bounded Treewidth Lemma Let C be a class of graphs of locally bounded treewidth. Then there is an algorithm that, given G ∈ C, a set S ⊆ V(G) and l, r ∈ N, decides if S is (l, r)-scattered in time g(l, r)|V(G)|. Proof: We now show that the treewidth of G[NG 2r [T])] is bounded by some function that depends only on l and r. Using Courcelle’s Theorem this implies the lemma. To see this note that the diameter of every component of NG 2r [T] is bounded by (4r + 1)l and hence every such component is contained in the (4r + 1)l neighborhood of any vertex in that component. Planar Graphs Locally Bounded Treewidth A Meta-Theorem for FO-Logic and Locally Bounded Treewidth Theorem Let C be a class of graphs with locally bounded treewidth and Φ be an FO-formula of length k. Then it can be decided in time f(k)O(n2) whether G |= Φ for every G ∈ C. Proof: Let Φ be the given FO-formula of length at most k and G ∈ C. Because of Gaifman’s Theorem we can assume that Φ has the form: Φ := ∃x1, . . . xl( 1≤i 2r ∧ 1≤i≤l φ(xi) with l, r ≥ 1 and r-local φ(x). Planar Graphs Locally Bounded Treewidth A Meta-Theorem for FO-Logic and Locally Bounded Treewidth Theorem Let C be a class of graphs with locally bounded treewidth and Φ be an FO-formula of length k. Then it can be decided in time f(k)O(n2) whether G |= Φ for every G ∈ C. Proof, continued: Because of Courcelle’s Theorem and the fact that C has bounded local treewidth can decide whether G |= φ(v) in time f(k)|V(G)| for every v ∈ V(G). Consequently, we can compute the set { v ∈ V(G) : G |= φ(v) } in time f(|φ|)|V(G)|2. Now, G |= φ iff S is (l, r)-scattered. Using the previous Lemma it follows that we can decide whether S is (l, r)-scattered in time g(k)|V(G)|. This shows the theorem. Planar Graphs Layer decompositions and Applications Outline 1 Planar Graphs Introduction Algorithms on Planar Graphs Locally Bounded Treewidth Layer decompositions and Applications Bidimensionality and Applications Planar Graphs Layer decompositions and Applications Outerplanar Graphs and Layers Let G be a plane graph. G is outerplanar or 1-outerplanar if every vertex is incident with the outer face. G is k-outerplanar for k ≥ 2 if deleting all vertices that are incident with the outer face yields a (k − 1)-outerplanar graph. Layer Decomposition: The vertices of a k-outerplanar graph can be partitioned into k layers L1, . . . , Lk as follows: L1 consists of the vertices incident with the outer face, and Li consists of the vertices incident with the outer face after deleting the vertex sets L1, . . . , Li−1. Planar Graphs Layer decompositions and Applications Outerplanar Graphs and Layers Proposition (1) Let L1, . . . , Lk be a layer decomposition of a k-outerplanar graph (G, Π), and let L = Li ∪ · · · ∪ Li+j. A tree decomposition of G[L] of width 3j + 3 can be found in polynomial time. Proof: Add a single vertex r drawn in the outer face of G[L] and connect it to every vertex in Li while maintaining a plane graph. Add edges to ensure that every vertex in layer Lx has a neighbor in layer Lx−1 while maintaining a plane graph. Call the resulting plane graph G . Then a BFS tree of G rooted at r has height j + 1, hence tw(G) ≤ tw(G ) ≤ 3j + 3. Planar Graphs Layer decompositions and Applications Outerplanar Graphs and Layers Proposition (2) Let S1, . . . , Sl be disjoint vertex sets of G and S := S1 ∪ · · · ∪ Sl such that: tw(G \ S) ≤ t, Every component of G \ S only has neighbors in Si and Si+1 for some i, there are no edges between Si and Sj if |j − i| ≥ 2, and |Si| ≤ x for every i. Then tw(G) ≤ t + 2x. Sets S1, . . . , Sl that satisfy the above properties are called t-x-separators. Planar Graphs Layer decompositions and Applications Outerplanar Graphs and Layers Proof: Construct a tree decomposition as follows: Start with a path on vertices v1, . . . , vl−1 and let X(vi) := Si ∪ Si+1. For every component C of G \ S that only has neighbors in Si and Si+1, add a tree decomposition of width t of C, add Si ∪ Si+1 to all bags, and connect this tree to vi with an arbitrary edge. This yields a tree decomposition of width t + 2x. Planar Graphs Layer decompositions and Applications Outerplanar Graphs and Layers Theorem A planar graph G on n vertices has tw(G) < 4.9 √ n. Proof: Consider a planar embedding of G and let k be its outerplanarity. Construct a layer decomposition L1, . . . , Lk . Let α = 3 2 < 1.225. Construct t-x-separators S1, . . . , Sl with t = 3 α √ n and x = α √ n as follows: Planar Graphs Layer decompositions and Applications Outerplanar Graphs and Layers Theorem A planar graph G on n vertices has tw(G) < 4.9 √ n. Proof: Consider the layers L1, . . . , Lk in order. Whenever |Li| ≤ x, this Li is chosen as the next Sj. Suppose b layers are not selected as separator. Then n ≥ bx = bα √ n, so b ≤ √ n/α. Therefore, tw(G \ S) ≤ 3b ≤ 3 α √ n by Proposition 1. Then by Proposition 2, tw(G) ≤ t + 2x ≤ 3 α √ n + 2α √ n = 4α √ n < 4.9 √ n. Planar Graphs Layer decompositions and Applications Some simple Applications The following algorithm decides in time 2O( √ k)nO(1) whether a planar graph G on n vertices admits a k-vertex cover: (1) In polynomial time reduce (G, k) to an equivalent (planar!) instance (G , k ) with n = |V(G )| ≤ 2k (See the kernelization lecture and note that the reduction rules preserve planarity). (2) Use the previous theorem to construct a tree decomposition of G of width w ∈ O( √ n) = O( √ k). (3) Use dynamic programming to decide whether G has a k -VC in time 2O( √ k)nO(1) (see lecture on dynamic programming over tree decompositions). Similarly, a 2O( √ k)nO(1) algorithm can be given for k-PLANAR INDEPENDENT SET because we have a 4k-vertex kernel (on planar graphs) and a 2w nO(1) dynamic programming algorithm from a previous lecture. Planar Graphs Layer decompositions and Applications Advanced Applications Recall that we had a 5k-vertex kernel for k-MAX LEAVES SPANNING TREE which used planarity preserving reduction rules. Question Can a 2O( √ k)nO(1) algorithm for k-PLANAR MAX LEAVES SPANNING TREE be given? Answer Yes, but in this case a 2O(w)nO(1) dynamic programming algorithm is far from trivial: such algorithms make heavy use of planarity! Planar Graphs Layer decompositions and Applications Advanced Applications Question Can this approach be used to give a fast FPT algorithm for planar problems without linear kernels? Answer Yes, by constructing the separators S1, . . . , Sl more smartly, and bounding their size in terms of an optimal solution. Planar Graphs Bidimensionality and Applications Outline 1 Planar Graphs Introduction Algorithms on Planar Graphs Locally Bounded Treewidth Layer decompositions and Applications Bidimensionality and Applications Planar Graphs Bidimensionality and Applications Grid Minors and Treewidth – General Graphs Recall: Gk×k denotes the k × k grid, which is a planar graph with tree width k. Recall: Graph H is a minor of graph G if H can be obtained from G by vertex deletions, edge deletions, and edge constractions. In that case tw(H) ≤ tw(G). Hence, if G has a Gk×k as a minor, then tw(G) ≥ k. Theorem Every graph of tree width at least w(k) := 202k5 has Gk×k as a minor. Planar Graphs Bidimensionality and Applications Grid Minors and Treewidth – General Graphs Theorem Let G be a graph that has a Gk×k as a minor. Then G has a k2-path. Planar Graphs Bidimensionality and Applications An FPT-algorithm for k-PATH Decide whether tw(G) ≤ w( √ k) and if so construct a tree decomposition. Use the tree decompostion to decide whether G has a k-path using an f(w( √ k))nO(1) dynamic programming algorithm. (which exists due to Courcelle’s Theorem). Otherwise, i.e., if tw(G) ≥ w( √ k) then return YES (This is correct by the previous theorem). This is by far the most unpractical and slowest FPT algorithm that we have seen yet! Planar Graphs Bidimensionality and Applications Bidimensionality – the General Framework The above scheme suggests that in order to prove that a problem admits an FPT algorithm, we only need to show: (1) For graphs with large grid minors the answer is trivially YES or NO. (2) The problem can be expressed in MSOL or otherwise solved efficiently on graphs of bounded treewidth. For many problems Properites (1) and (2) can be easily verified (e.g., k-MLST, k-FVS, k-VC). Not surprisingly, Property (1) above does not hold for problems such as k-INDEPENDENT SET or k-DOMINATING SET. Next: For planar and related graph classes the above scheme gives fast and practical FPT algorithm even for k-INDEPENDENT SET and k-DOMINATING SET. Planar Graphs Bidimensionality and Applications Bidimensionality for Planar Graphs Theorem Every planar graph of treewidth at least 6k − 5 has a Gk×k as a minor. Theorem Let G be a planar graph. In polynomial time, a tree decomposition of G of width at most 3 2 tw(G) can be constructed, i.e, treewidth is constant factor approximable on planar graphs. Planar Graphs Bidimensionality and Applications Bidimensionality for Planar Graphs Suppose that for a parameterized planar graph problem the following properties hold: (A) for graphs with Gc×c minor the answer is trivially YES or NO, where c ∈ O( √ k), and (B) When a tree decomposition of width w is given, the problem can be solved in time 2O(w)nO(1). Then the following algorithm is a 2O( √ k)nO(1) FPT algorithm: (1) In polynomial time, compute a 3/2-approximate tree decomposition (T, X) of G. (2) If the width of (T, X) is at least O( √ k), then return the trivial answer. (3) If the width of (T, X) is at most O( √ k), then solve the problem by dynamic programming. Problems that satisfy Property (A) are called bidimensional. Planar Graphs Bidimensionality and Applications k-VERTEX COVER is bidimensional Proposition If a graph G contains a Gk×k as a minor, then G has no vertex cover smaller than k(k − 1)/2. Theorem k-PLANAR VERTEX COVER can be solved in time O(2O( √ k)nO(1). Planar Graphs Bidimensionality and Applications Contraction Bidimensionality Some definitions: Graph H is a contraction minor of G if it can be obtained from G by only using edge contractions. A connected plane graph H is a partially triangulated k × k-grid if E(Gk×k ) ⊆ E(H) ⊆ E(G) holds for some triangulation G of Gk×k . Planar Graphs Bidimensionality and Applications Contraction Bidimensionality Proposition If a planar graph G has Gk×k as a minor, then it has a partially triangulated k × k-grid as a contraction minor. Proof: Apply the contractions that obtain Gk×k from G but not the deletions. The result is a planar graph H with V(H) = V(Gk×k ) and E(Gk×k ) ⊆ E(H). H can be triangulated by adding more edges. The statement follows. Planar Graphs Bidimensionality and Applications k-PLANAR DOMINATING SET IS BIDIMENSIONAL Proposition If a planar graph G contains Gk×k as a minor, then G has no dominating set of size less than (k − 2)2/9. Proof: By the previous proposition, G has a partially triangulated k × k-grid H as a contraction minor. Let the vertices of Gk×k be labeled vij with i, j ∈ {1, . . . , k}. The vertices vij of H with 2 ≤ i ≤ k − 1 and 2 ≤ j ≤ k − 1 are called internal vertices of H. Planar Graphs Bidimensionality and Applications k-PLANAR DOMINATING SET IS BIDIMENSIONAL Proposition If a planar graph G contains Gk×k as a minor, then G has no dominating set of size less than (k − 2)2/9. Proof, continued: Let S be a minimum dominating set of H. Any vertex of S dominates at most 9 internal vertices of H, hence |S| ≥ (k − 1)2/9. If G has a dominating set S, and G is obtained from G by contracting {u, v} into w, then: (1) if u, v /∈ S, then S is a dominating set of G , and (2) if u ∈ S or v ∈ S, then S − u − v + w is a dominating set of G . Planar Graphs Bidimensionality and Applications k-PLANAR DOMINATING SET IS BIDIMENSIONAL Theorem k-PLANAR DOMINATING SET can be solved in time O(2O( √ k)nO(1). Planar Graphs Bidimensionality and Applications Planar Graphs, Layers, and Grid Minors – Summary Many problems that (probably) do not allow FPT algorithms in general do admit FPT algorithms when restricted to planar graphs (e.g. k-INDEPENDENT SET, k-DOMINATING SET) 2 general methods to obtain (fast) FPT algorithms for problems of planar graphs: layer decompositions and bidimensionality/grid minors The layer decomposition methods tends to be faster and easier to implement. The bidimensionality/grid minor method is stronger, and gives easier proofs. Even for general graphs considering grid minors is useful for proving that an FPT algorithm exists. Planar Graphs Bidimensionality and Applications Planar Graphs, Layers, and Grid Minors – Summary To obtain subexponential FPT algorithms for planar graphs, we need: (A) either a linear kernel (layers) or a bidimensionality proof (grid minors). (B) A dynamic programming algorithm with parameter function 2O(tw(G)) , and Bidimensionality gives fast FPT algorithms for many other graph classes that are closed under taking minors!