What is the initialization time of a link-cut tree?

Question

Link-cut tree is a data structure invented by Sleator and Tarjan, which supports various operations and queries on a $n$-node forest in time $O(\log n)$. (For example, operation link combines two trees in the forest into one, while operation cut divide a tree in the forest into two trees.)

Several applications are known by using link-cut trees, and here I'm particularly interested in Goodrich's separator decomposition, which given a $n$-node plane graph $G$ one can obtain a corresponding binary tree where nodes are subgraphs of $G$, and the children of a node $H$ are the subgraphs of $H$ divided by the separator on $H$. Such a decomposition can be easily constructed in $O(n \log n)$ time (since a separator can be found in $O(n)$ time, and since the separator divides the graph so balanced, after $O(\log n)$ level of separations the leaves of the tree are of size $O(1)$). The main contribution of Goodrich is that he can construct such a decomposition in time $O(n)$, by maintaining and reusing the data structures used for finding separators in each level.

One of the data structures being used in the construction, is indeed the link-cut tree. In page 7 of the paper by Goodrich, he claimed that the initialization of the link-cut tree can be done in time $O(n)$. While I go through all the papers cited there, it seems to me that if we construct a link-cut tree via operation link, it takes time $O(n \log n)$ in total.

Do I misunderstand something? Can the initialization of a link-cut tree be done in time $O(n)$?

Answer 1

Many thanks to Hsueh-I Lu, my teacher in National Taiwan University, who provides the following solution.

It turns out that the answer is rather simple; in the initialization of a data structure, we don't have to construct the structure by the queries and operations it supports. Of course, we cannot perform queries during the construction like we usually do if we build the tree by link operation; but in this separator decomposition application we don't need it.

That is to say, in the application to the separator decomposition, when we have to construct the link-cut trees L(T) for the spanning tree T on input graph G, instead of computing the structures and values of the trees L(T) by link operation, we directly compute the heavy-light path decomposition of the tree T, and construct the corresponding binary tree structure for each paths, and gluing the binary trees according to the path decomposition. All the steps can be done in linear time.

For each necessary values on the nodes of L(T), since each value can be compute from T in linear time (in this application), instead of assigning values on binary tree structures and updating when gluing the trees, we assign the precomputed values directly onto the nodes of the final link-cut trees L(T). There are only a constant type of values need to be assigned, and again this can be done in linear time.

Answer 2

Chapter 5.1 in "Data Structures and Network Algorithms", which is ref. 43 in the paper you cited, seems like it might have the answer:

http://books.google.com/books?id=JiC7mIqg-X4C&lpg=PP1&ots=8frbjj8vL0&dq=data%20structures%20and%20network%20algorithms&pg=PA59#v=onepage&q&f=false

...In discussing this problem we shall use 'm' to denote the number of operations and 'n' to denote the numebr of vertices (maketree operations). One way to solve this problem is to store with each vertex its parent and its cost. With this representation each maketree, link, or cut operation takes O(1) time, and each findroot, findcost, or addcost operation takes time proportiatonl to the depth of the input vertex, which is O(n)...

Several more successive pages are available in the preview.