Planar embeddability of the vertices of a graph using a fixed point set is NP-hard

Planar embeddability of the vertices of a graph using a fixed point set is NP-hard 1 Sergio Cabello Institute of Information and Computing Sciences Utrecht University The Netherlands Abstract Let G= (V, E) be a graph with nvertices and let Pbe a set of npoints in the plane. We show that deciding whether there is a planar straight-line embedding of Gsuch that the vertices Vare embedded onto the points P is NP-complete, even when Gis 2-connected and 2-outerplanar. This settles an open problem posed in [2,4,14]. 1. Introduction Ageometric graph His a graph G(H) together with an injective mapping of its vertices into the plane. An edge of the graph is drawn as a straightline segment joining its vertices. We use V(H) for the set of points where the vertices of G(H) are mapped to, and we do not make a distinction between the edges of G(H) and H. A planar geometric graph is a geometric graph such that its edges intersect only at common vertices. In this case, we say that His a geometric planar embedding of G(H). See [15] for a survey on geometric graphs. Let Pbe a set of npoints in the plane, and let G be a graph with nvertices. What is the complexity of deciding if there is a straight-line planar embedding of Gsuch that the vertices of Gare mapped onto P? This question has been posed as open problem in [2,4,14], and here we show that this decision problem is NP-complete. Let us rephrase the result in terms of geometric graphs. Theorem 1 Let Pbe a set of npoints, and let G be a graph on nvertices. Deciding if there exists a geometric planar embedding Hof Gsuch that V(H) = Pis an NP-complete problem. The reduction is from 3-partition, a strongly NP- hard problem to be described below, and it constructs a 2-connected graph G. The main ideas of Email address: [email protected] (Sergio Cabello). 1Partially supported by the Cornelis Lely Stichting. A full version is available as [5]. the proof are given in Section 2, and we use that the maximal 3-connected blocks of a 2-connected planar graph can be embedded in different faces. In a 3-connected planar graph, all planar embeddings are topologically equivalent due to Whitney’s theorem [10, Chapter 6]. Therefore, it does not seem possible to extend our technique to show the hardness for 3-connected planar graphs. Related work A few variations of the problem of embedding a planar graph into a fixed point set have been considered. The problem of characterizing what class of graphs can be embedded into any point set in general position (no three points being collinear) was posed in [12]. They showed that the answer is the class of outerplanar graphs, that is, graphs that admit a straight-line planar embedding with all vertices in the outerface. This result was rediscovered in [6], and efficient algorithms for constructing such an embedding for a given graph and a given point set are described in [2]. The currently best algorithm runs in O(nlog3n) time, although the best known lower bound is Ω(nlog n). A tree is a special case of outerplanar graph. In this case, we also can choose to which point the root should be mapped. See [3,13,16] for the evolution on this problem, also from the algorithmical point of view. For this setting, there are algorithms running in O(nlog n) time, which is worst case optimal. Bipartite embeddings of trees were considered in [1]. 20th EWCG Seville, Spain (2004) 20th European Workshop on Computational Geometry (B+3)n     v0 v1 v2 v3      a1 . . .      ai . . .      a3n . . . . . . . . . . . .        n−1times . . . Bi Tn−1 Fig. 1. Graph Gfor the NP-hardness reduction. If we allow each edge to be represented by a polygonal path with at most two bends, then it is always possible to get a planar embedding of a planar graph that maps the vertices to a fixed point set [14]. If a bijection between the vertices and the point set is fixed, then we need O(n2) bends in total to get a planar embedding of the graph, which is also asymptotically tight in the worst case [17]. We finish by mentioning a related problem, which was the initial motivation for this research. A universal set for graphs with nvertices is a set of points Snsuch that any planar graph with nvertices has a straight-line planar embedding whose vertices are a subset of Sn. Asymptotically, the smallest universal set is known to have size at least 1.098n[7], and it is bounded by O(n2) [8,18]. Characterizing the asymptotic size of the smallest universal set is an interesting open problem [9, Problem 45]. 2. Planar embeddability is NP-complete It is clear that the problem belongs to NP: a geometric graph Hwith V(H) = Pand G(H)≡G can be described by the bijection between V(G) and P, and for a given bijection we can test in polynomial time whether it actually is a planar geometric graph; therefore, we can take as certificate the bijection between V(G) and P. For showing the NP-hardness, the reduction is from 3-partition. Problem: 3-partition Input: A natural number B, and 3nnatural numbers a1,...,a3nwith B 4< ai<B 2. Output: ndisjoint sets S1,...,Snsuch that for all Sjwe have Sj⊂ {a1,...,a3n},|Sj|= 3, and Pa∈Sja=B. We will use that 3-partition is a strongly NP-hard problem, that is, it is NP-hard even if Bis bounded by a polynomial in n[11]. Observe that because B 4< ai<B 2, it does not make sense to have sets March 25-26, 2004 Seville (Spain) . . .                                                                            ntimes p0p2 p3      B . . .      B      n . . . . . . . . . . . . . . . . . . 0 1 K2K 0 −1 −n K      B . . . p1 Fig. 2. Point set Pfor the NP-hardness reduction. K= (B+ 2)n. Sjwith fewer or more than 3 elements. That is, it is equivalent to ask for subdividing all the numbers into disjoint sets that sum to B. Of course, we can assume that P3n i=1 ai=Bn, as otherwise it is impossible that a solution exists. In the following, we only give the reduction, and do not discuss how the solution to the constructed problem relates to the original problem. Details can be found in the full version [5]. Given a 3-partition instance, we construct the following graph G(see Figure 1): – Start with a 4-cycle with vertices v0, . . . , v3, and edges (vi−1, vimod 4). The vertices v0and v2will play a special role. – For each aiin the input, make a path Biconsisting of aivertices, and put an edge between each of those vertices and the vertices v0, v2. – Construct n−1 triangles T1,...,Tn−1. For each triangle Ti, put edges between each of its vertices and v2, and edges between two of its vertices and v0. We call each of these structures a separator (the reason for this will become clear later). – Make a path Cof (B+ 3)nvertices, and put edges between each of the vertices in Cand v0. Furthermore, put an edge between one end of the path and v1, and another edge between the other end and v3. It is easy to see that Gis planar; in fact, we are giving a planar embedding of it in Figure 1. The idea is to design a point set Psuch that G\(B1∪ · · · ∪ B3n) can be embedded onto Pin essentially one way. Furthermore, the embedding of G\(B1∪ · · ·∪B3n) will decompose the rest of the points into ngroups, each of Bvertices and lying in a different face. The embedding of the remaining vertices B1∪ · · · ∪ B3nwill be possible in a planar way if and only if the paths Bican be decomposed into groups of exactly Bvertices, which is equivalent to the original 3-partition instance. The following point set Pdoes the work (see Figure 2): – Let K:= (B+ 2)n. – Place (B+ 3)npoints at the coordinates (0,−n),(0,−(n−1)),...,(0,−1) and at the coordinates (0,1),(0,2),...,(0, K). – Place points p0:= (1,0), p1:= (K, K), p2:= (2K, 0), p3:= (K, −n). In the figure, these points are shown as boxes and are labeled. – For each i∈ {0,...,n−1}, place the group of Bpoints (K, −2 + (B+ 2)i+ 1),(K, −2 + (B+ 2)i+ 2),...,(K, −2 + (B+ 2)i+B). – For each i∈ {1,...,n−1}, place the group of three points (K, (B+ 2)i−3),(K, (B+ 2)i− 2),...,(K+ 1,(B+ 2)i−3). In the figure, these points are shown as empty circles. 3. Concluding remarks The point set Pthat we have constructed has many collinear points. However, in the proof we do not use this fact, and so it is easy to modify the reduction in such a way that no three points of P are collinear. Probably, the easiest way for keeping 20th European Workshop on Computational Geometry integer coordinates is replacing each of the points lying in a vertical line by points lying in a parabola, and adjusting the value Kaccordingly. Therefore, the result remains valid even if Pis in general position, meaning that no 3 points are collinear. In the proof, the graph Gthat we constructed is 2-outerplanar, as shown in Figure 1. kouterplanarity is a generalization of outerplanarity that is defined inductively. A planar embedding of a graph is k-outerplanar if removing the vertices of the outer face produces a (k−1)-outerplanar embedding, where 1-outerplanar stands for an outerplanar embedding. A graph is k-outerplanar if it admits a k-outerplanar embedding. For outerplanar graphs, the embedding problem is polynomially solvable [2], but for 2-outerplanar we showed that it is NP-complete. Therefore, regarding outerplanarity, our result is tight. The graph Gthat we constructed in the proof is 2-connected; removing the vertices v1, v3discon- nects the graph. As mentioned in the introduction, we use this fact in the proof because in a 2- connected graph the maximal 3-connected blocks can flip from one face to another one. Therefore, it would be interesting to find out the complexity of the problem when the graph Gis 3-connected, and more generally, the complexity when the topology of the embedding is specified beforehand. Acknowledgements I would like to thank Marc van Kreveld for careful reading of the manuscript and pointing out that the reduction can use a 2-outerplanar graph. References [1] M. Abellanas, J. Garc´ıa-L´opez, G. Hern´andez, M. Noy, and P. A. Ramos. Bipartite embeddings of trees in the plane. Discrete Applied Mathematics, 93:141– 148, 1999. A preliminary version appeared in Graph Drawing (Proc. GD ’96), LNCS 1190, pg. 1–10. [2] P. Bose. On embedding an outer-planar graph in a point set. Comput. Geom. Theory Appl., 23:303–312, November 2002. A preliminary version appeared in Graph Drawing (Proc. GD ’97), LNCS 1353, pg. 25– 36. [3] P. Bose, M. McAllister, and J. Snoeyink. Optimal algorithms to embed trees in a point set. Journal of Graph Algorithms and Applications, 1(2):1–15, 1997. A preliminary version appeared in Graph Drawing (Proc. GD ’95), LNCS 1027, pg. 64–75. [4] F. Brandenberg, D. Eppstein, M.T. Goodrich, S.G. Kobourov, G. Liotta, and P. Mutzel. Selected open problems in graph drawing. In Graph Drawing (Proc. GD’03), LNCS, 2003. To appear. [5] S. Cabello. Planar embeddability of the vertices of a graph using a fixed point set is NP-hard. Technical report UU-CS-2003-031. Available at http://www.cs.uu.nl/research/techreps/ UU-CS-2003-031.html, 2003. [6] N. Castaneda and J. Urrutia. Straight line embeddings of planar graphs on point sets. In Proc. 8th Canad. Conf. Comput. Geom., pages 312–318, 1996. [7] M. Chrobak and H. Karloff. A lower bound on the size of universal sets for planar graphs. SIGACT News, 20:83–86, 1989. [8] H. de Fraysseix, J. Pach, and R. Pollack. How to draw a planar graph on a grid. Combinatorica, 10(1):41–51, 1990. [9] E. D. Demaine, J. S. B. Mitchell, and J. O’Rourke (eds.). The Open Problems Project. http://cs. smith.edu/~orourke/TOPP/Welcome.html. [10] R. Diestel. Graph Theory. Springer-Verlag, New York, 2nd edition, 2000. [11] M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP- Completeness. W. H. Freeman, New York, NY, 1979. [12] P. Gritzmann, B. Mohar, J. Pach, and R. Pollack. Embedding a planar triangulation with vertices at specified points. Amer. Math. Monthly, 98(2):165–166, 1991. [13] Y. Ikebe, M. A. Perles, A. Tamura, and S. Tokunaga. The rooted tree embedding problem into points in the plane. Discrete Comput. Geom., 11:51–63, 1994. [14] M. Kaufmann and R. Wiese. Embedding vertices at points: Few bends suffice for planar graphs. Journal of Graph Algorithms and Applications, 6(1):115–129, 2002. A preliminary version appeared in Graph Drawing (Proc. GD ’99), LNCS 1731, pg. 165–174. [15] J. Pach. Geometric graph theory. In J. D. Lamb and D. A. Preece, editors, Surveys in Combinatorics, number 267 in London Mathematical Society Lecture Note Series, pages 167–200. Cambridge University Press, 1999. [16] J. Pach and J. T¨oumlr˝ocsik. Layout of rooted trees. In W.T. Trotter, editor, Planar Graphs, volume 9 of DIMACS Series, pages 131–137. Amer. Math. Soc., Providence, 1993. [17] J. Pach and R. Wenger. Embedding planar graphs at fixed vertex locations. Graphs Combin., 17:717– 728, 2001. A preliminary version appeared in Graph Drawing (Proc. GD ’98), LNCS 1547, pg. 263–274. [18] W. Schnyder. Embedding planar graphs on the grid. In Proc. 1st ACM-SIAM Sympos. Discrete Algorithms, pages 138–148, 1990.