Point-Set Embeddability of 2-Colored Trees

Frati, Fabrizio and Glisse, Marc and Lenhart, William J. and Liotta, Giuseppe and Mchedlidze, Tamara and Nishat, Rahnuma Islam (2013) Point-Set Embeddability of 2-Colored Trees. In: 20th International Symposium, GD 2012, September 19-21, 2012, Redmond, WA, USA , pp. 291-302 (Official URL: http://link.springer.com/chapter/10.1007/978-3-642-36763-2_26).

Full text not available from this repository.


In this paper we study bichromatic point-set embeddings of 2-colored trees on 2-colored point sets, i.e., point-set embeddings of trees (whose vertices are colored red and blue) on point sets (whose points are colored red and blue) such that each red (blue) vertex is mapped to a red (resp. blue) point. We prove that deciding whether a given 2-colored tree admits a bichromatic point-set embedding on a given convex point set is an  -complete problem; we also show that the same problem is linear-time solvable if the convex point set does not contain two consecutive points with the same color. Furthermore, we prove a 3n/2 − O(1) lower bound and a 2n upper bound (a 7n/6 − O(logn) lower bound and a 4n/3 upper bound) on the minimum size of a universal point set for straight-line bichromatic embeddings of 2-colored trees (resp. 2-colored binary trees). Finally, we show that universal convex point sets with n points exist for 1-bend bichromatic point-set embeddings of 2-colored trees.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-36763-2_26
Classifications:G Algorithms and Complexity > G.490 Embeddings
ID Code:1318

Repository Staff Only: item control page


Abellanas, M., Garcia-Lopez, J., Hernández-Peñalver, G., Noy, M., Ramos, P.A.: Bipartite embeddings of trees in the plane. Discr. Appl. Math. 93(2-3), 141–148 (1999)

Badent, M., Di Giacomo, E., Liotta, G.: Drawing colored graphs on colored points. Theor. Comp. Sci. 408(2-3), 129–142 (2008)

Biedl, T., Vatshelle, M.: The point-set embeddability problem for plane graphs. In: SoCG 2012 (2012) (to appear)

Binucci, C., Di Giacomo, E., Didimo, W., Estrella-Balderrama, A., Frati, F., Kobourov, S.G., Liotta, G.: Upward straight-line embeddings of directed graphs into point sets. Computat. Geom. Th. Appl. 43, 219–232 (2010)

Bose, P.: On embedding an outer-planar graph in a point set. Comput. Geom. Th. Appl. 23(3), 303–312 (2002)

Bose, P., McAllister, M., Snoeyink, J.: Optimal algorithms to embed trees in a point set. J. Graph Alg. Appl. 1(2), 1–15 (1997)

Brandes, U., Erten, C., Estrella-Balderrama, A., Fowler, J.J., Frati, F., Geyer, M., Gutwenger, C., Hong, S., Kaufmann, M., Kobourov, S.G., Liotta, G., Mutzel, P., Symvonis, A.: Colored simultaneous geometric embeddings and universal pointsets. Algorithmica 60(3), 569–592 (2011)

Cabello, S.: Planar embeddability of the vertices of a graph using a fixed point set is NP-hard. J. Graph Algorithms Appl. 10(2), 353–366 (2006)

Chrobak, M., Karloff, H.: A lower bound on the size of universal sets for planar graphs. SIGACT News 20, 83–86 (1989)

de Fraysseix, H., Pach, J., Pollack, R.: How to draw a planar graph on a grid. Combinatorica 10, 41–51 (1990)

Di Giacomo, E., Didimo, W., Liotta, G., Meijer, H., Trotta, F., Wismath, S.K.: k-colored point-set embeddability of outerplanar graphs. J. Graph Alg. Appl. 12(1), 29–49 (2008)

Di Giacomo, E., Didimo, W., Liotta, G., Meijer, H., Wismath, S.K.: Point-set embeddings of trees with given partial drawings. Comput. Geom. 42(6-7), 664–676 (2009)

Di Giacomo, E., Didimo, W., Liotta, G., Wismath, S.: Curve-constrained drawings of planar graphs. Comput. Geom. Theory Appl. 30, 1–23 (2005)

Di Giacomo, E., Liotta, G., Trotta, F.: On embedding a graph on two sets of points. Int. J. of Found. Comp. Sci. 17(5), 1071–1094 (2006)

Di Giacomo, E., Liotta, G., Trotta, F.: Drawing colored graphs with constrained vertex positions and few bends per edge. Algorithmica 57, 796–818 (2010)

Dujmovic, V., Evans, W., Lazard, S., Lenhart, W., Liotta, G., Rappaport, D., Wismath, S.: On Point-Sets That Support Planar Graphs. In: van Kreveld, M., Speckmann, B. (eds.) GD 2011. LNCS, vol. 7034, pp. 64–74. Springer, Heidelberg (2012)

Durocher, S., Mondal, D.: On the Hardness of Point-Set Embeddability (Extended Abstract). In: Rahman, M. S., Nakano, S.-I. (eds.) WALCOM 2012. LNCS, vol. 7157, pp. 148–159. Springer, Heidelberg (2012)

Estrella-Balderrama, A., Fowler, J.J., Kobourov, S.G.: Colored simultaneous geometric embeddings and universal pointsets. In: CCCG 2009, pp. 17–20 (2009)

Everett, H., Lazard, S., Liotta, G., Wismath, S.K.: Universal sets of n points for one-bend drawings of planar graphs with n vertices. Discr. Comp. Geom. 43(2), 272–288 (2010)

van Garderen, M., Liotta, G., Meijer, H.: Universal point sets for 2-coloured trees. Inf. Process. Lett. 112(8-9), 346–350 (2012)

Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1979)

Gritzmann, P., Mohar, B., Pach, J., Pollack, R.: Embedding a planar triangulation with vertices at specified positions. The American Mathematical Monthly 98, 165–166 (1991)

Ikebe, Y., Perles, M.A., Tamura, A., Tokunaga, S.: The rooted tree embedding problem into points in the plane. Discr. Comp. Geom. 11, 51–63 (1994)

Kaneko, A., Kano, M.: Straight-line embeddings of two rooted trees in the plane. Discr. Comp. Geom. 21(4), 603–613 (1999)

Kaneko, A., Kano, M.: Straight line embeddings of rooted star forests in the plane. Discr. Appl. Math. 101(1-3), 167–175 (2000)

Kaneko, A., Kano, M.: Semi-balanced partitions of two sets of points and embeddings of rooted forests. Int. J. Comput. Geometry Appl. 15(3), 229–238 (2005)

Kaufmann, M., Wiese, R.: Embedding vertices at points: Few bends suffice for planar graphs. J. Graph Alg. Appl. 6(1), 115–129 (2002)

Kurowski, M.: A 1.235 lower bound on the number of points needed to draw all n-vertex planar graphs. Information Processing Letters 92(2), 95–98 (2004)

Pach, J., Wenger, R.: Embedding planar graphs at fixed vertex locations. Graphs and Combinatorics 17(4), 717–728 (2001)