Maintaining alterable planar embeddings of dynamic graphs – Københavns Universitet

Maintaining alterable planar embeddings of dynamic graphs

Master thesis defence by Eva Rotenberg

Abstract:

We present a data structure for maintaining a planar embedding of a dynamic plane graph. The graph may be updated with edge deletions and insertions of edges when it does not violate the embedding. Queries of vertex pairs return the list of possible places for inserting an edge. Furthermore, the embedding may be updated with flips that alter the embedding by swapping the orientation of a subgraph, if the subgraph has certain properties of being not too well connected to the rest of the graph. All operations run in time O(lg(n)^2), where n is the number of vertices in the graph. We do this using top-trees, and using elegant properties about the dual graph.

Previous best result in this direction was by Italiano et al.(1), a data structure using topology trees which supports edge deleting, edge insertion (when compatible with the embedding), and query. They have a running time of O(lg(n)^2) per update, but their construction did not allow for alterations of the embedding.

A new lower bound for planarity testing is presented, namely Omega(lg(n)) for the slowest operation. The previous best lower bound was Omega(lg(n)/lg(lg(n))) by Henzinger et al.(2).

(1) http://link.springer.com/chapter/10.1007%2F3-540-57273-2_57

(2) http://link.springer.com/article/10.1007%2FPL00009228

Place: Lille UP1, Universitetsparken 1.

Time: February 18, 2pm.

Censor: Rolf Fagerberg (IMADA, SDU).

Supervisor: Christian Wulff-Nilsen.