Efficiently determine relative ordering between two elements in a PO-set

Question

What algorithms/heuristics exist for efficiently determining the relative order between two elements in a partially ordered set?

In my case, the PO-set is stored as a directed acyclic graph where an edge is an happened before relation and I am streaming live data into this PO-set. Nodes usually have less than 5 backward edges, with 1 being the most common, and there will be at most 10^6 nodes. The newly inserted nodes usually have edges to the previously most recently inserted nodes.

I am usually doing this query just after I've added a node to the graph, to find the relative ordering between the inserted node and a few select other nodes, so the traversal paths tend to overlap a lot. I am also maintaining a total order of the PO-set as I go, which might be useful for this as well.

My current solution consists of starting at both nodes and moving backwards one step at a time from both simultaneously (or rather, one step for the left node, then one step for the right) until I find a common ancestor node, or run out of edges to traverse. This is not very fast, but I don't have that many elements in the set yet so it works for now.

The main problem is the worst case runtime of O(n) as n will grow in the future. Is there a way to do this faster?