Kinetic and Stationary PointSet Embeddability for Plane GraphsRahmati, Zahed and Whitesides, Sue and King, Valerie (2013) Kinetic and Stationary PointSet Embeddability for Plane Graphs. In: 20th International Symposium, GD 2012, September 1921, 2012 , pp. 279290(Official URL: http://link.springer.com/chapter/10.1007/9783642...). Full text not available from this repository.
Official URL: http://link.springer.com/chapter/10.1007/9783642...
AbstractWe investigate a kinetic version of pointset 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 pointset 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 slowgrowing function and $λ_s (n)$ is the maximum length of DavenportSchinzel sequences of order s on n symbols.
Actions (login required)
