Kinetic and Stationary Point-Set Embeddability for Plane Graphs

Rahmati, Zahed and Whitesides, Sue and King, Valerie (2013) Kinetic and Stationary Point-Set Embeddability for Plane Graphs. In: 20th International Symposium, GD 2012, September 19-21, 2012, Redmond, WA, USA , pp. 279-290 (Official URL:

Full text not available from this repository.


We investigate a kinetic version of point-set embeddability. Given a plane graph $G(V,E) where |V| = n$, and a set P of n moving points where the trajectory of each point is an algebraic function of constant maximum degree s, we maintain a point-set embedding of G on P with at most three bends per edge during the motion. This requires reassigning the mapping of vertices to points from time to time. Our kinetic algorithm uses linear size, O(nlogn) preprocessing time, and processes $O(n^2 β_2s+2 (n)logn)$ events, each in$ O(log^2 n)$ time. Here, $β_s (n) = λ_s (n)/ n$ is an extremely slow-growing function and $λ_s (n)$ is the maximum length of Davenport-Schinzel sequences of order s on n symbols.

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

Repository Staff Only: item control page


Abam, M.A., Rahmati, Z., Zarei, A.: Kinetic Pie Delaunay Graph and Its Applications. In: Fomin, F.V., Kaski, P. (eds.) SWAT 2012. LNCS, vol. 7357, pp. 48–58. Springer, Heidelberg (2012)

Agarwal, P.K., Eppstein, D., Guibas, L.J., Henzinger, M.R.: Parametric and kinetic minimum spanning trees. In: FOCS, pp. 596–605. IEEE Computer Society (1998)

Agarwal, P.K., Kaplan, H., Sharir, M.: Kinetic and dynamic data structures for closest pair and all nearest neighbors. ACM Trans. Algorithms 5, 4:1–4:37 (2008)

Basch, J.: Kinetic data structures. PhD Thesis, Stanford University (1999)

Basch, J., Guibas, L.J., Hershberger, J.: Data structures for mobile data. In: Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1997, pp. 747–756. Society for Industrial and Applied Mathematics (1997)

Biedl, T., Vatshelle, M.: The point-set embeddability problem for plane graphs. In: Proceedings of the 28th Symposuim on Computational Geometry, SoCG 2012, pp. 41–50. ACM, New York (2012)

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

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

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–363 (2006)

Chen, C.: Any maximal planar graph with only one separating triangle is hamiltonian. J. Comb. Optim. 7(1), 79–86 (2003)

Chiba, N., Nishizeki, T.: The hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs. J. Algorithms 10(2), 187–211 (1989)

Chiba, N., Nishizeki, T.: Arboricity and subgraph listing algorithms. SIAM J. Comput. 14(1), 210–223 (1985)

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

Giacomo, E.D., Didimo, W., Liotta, G., Wismath, S.K.: Curve-constrained drawings of planar graphs. Computational Geometry 30(1), 1–23 (2005)

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

Guibas, L.J., Mitchell, J.S.B.: Voronoi Diagrams of Moving Points in the Plane. In: Schmidt, G., Berghammer, R. (eds.) WG 1991. LNCS, vol. 570, pp. 113–125. Springer, Heidelberg (1992)

Helden, G.: Each maximal planar graph with exactly two separating triangles is hamiltonian. Discrete Applied Mathematics 155(14), 1833–1836 (2007)

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

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

Nivasch, G.: Improved bounds and new techniques for Davenport–Schinzel sequences and their generalizations. J. ACM 57, 17:1–17:44 (2010)

Rahmati, Z., Zarei, A.: Kinetic Euclidean minimum spanning tree in the plane. Journal of Discrete Algorithms 16, 2–11 (2012)

Sharir, M., Agarwal, P.K.: Davenport-Schinzel Sequences and their Geometric Applications. Cambridge University Press, New York (2010)

Tutte, W.: A theorem on planar graphs. Trans. Amer. Math. Soc. 82, 99–116 (1956)

Whitney, H.: A theorem on graphs. Ann. Math. 32, 378–390 (1931)