# Has there been any work done on incremental connectivity in path graphs?

This set of lecture notes describes a data structure for decremental connectivity in path graphs that supports queries and removals in amortized O(1) each. Has there been any work done on incremental connectivity on path graphs? Using a disjoint-set forest it's possible to do queries and insertions in amortized O(α(n)) time each, but can that be sped up using the fact that we're only looking at a path graph, not a general graph?

Thanks!

• If you are given the sequence of vertices $v_1,\ldots,v_n$, and you can only add edges between $v_i$ and $v_{i+1}$, then $O(1)$ time seems possible. Otherwise maybe modifying the lower bound for disjoint-set data structure can get you the lower bound. – Chao Xu Jan 20 '16 at 21:54