Efficiently determine relative ordering between two elements in a PO-set
This is the dynamic reachability problem for DAGs, where you only need to handle vertex/edge insertion (but not deletion).  It's sometimes known as incremental reachability or incremental DAG reachability.

There's lots written in the research literature on the subject.  Here are some pointers to get you started:


https://cstheory.stackexchange.com/q/18787/5038
https://cstheory.stackexchange.com/q/14343/5038
https://cstheory.stackexchange.com/q/5176/5038
https://cstheory.stackexchange.com/q/29/5038
https://en.wikipedia.org/wiki/Dynamic_problem_(algorithms)
https://en.wikipedia.org/wiki/Dynamic_connectivity (though this seems to talk about undirected graphs, rather than directed graphs)