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 , 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

Actions (login required)

View Item View Item