Computer Science – Data Structures and Algorithms
Scientific paper
2002-07-24
Computer Science
Data Structures and Algorithms
13 pages, 2 figures
Scientific paper
We provide a data structure for maintaining an embedding of a graph on a surface (represented combinatorially by a permutation of edges around each vertex) and computing generators of the fundamental group of the surface, in amortized time O(log n + log g(log log g)^3) per update on a surface of genus g; we can also test orientability of the surface in the same time, and maintain the minimum and maximum spanning tree of the graph in time O(log n + log^4 g) per update. Our data structure allows edge insertion and deletion as well as the dual operations; these operations may implicitly change the genus of the embedding surface. We apply similar ideas to improve the constant factor in a separator theorem for low-genus graphs, and to find in linear time a tree-decomposition of low-genus low-diameter graphs.
No associations
LandOfFree
Dynamic Generators of Topologically Embedded Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Dynamic Generators of Topologically Embedded Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dynamic Generators of Topologically Embedded Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-293612