DAG: When adding an edge that would normally result in a cycle, is there an algorithm to split the graph instead?
Any graph of this type can be represented using this simplified model (left):

where M1, M2, and M3 are metanodes that can represent 0 or more nodes, and edges involving M1, M2, and M3 can represent 0 or more edges.
In order to split the graph in the manner I am seeking, it's required to classify these nodes using the reachability algorithm.  The members of M1 are all nodes $k \not \in \{A, B\}$ such that $A \not \le k$.  The members of M2 are all nodes $k \not \in \{A, B\}$ such that $A \le k \land B \not \le k$.  Finally the members of M3 are the remaining nodes $k \not \in \{A, B\}$ and $B \le k$.
The members of M2 are duplicated along with B and A.  All edges from M1 to M2 or B are routed to M2' and B' instead.  And the edges from M2 and B to
M3 are duplicated for M2' and B'.  Finally, an edge from B' to A' is made.
The algorithm fails to place A' if and only if there are no edges connecting M1 to B and there are no edges from M1 to M2 or M2 to B, which represents the fact that there is no path to B without going through A, so there is no possible way to place A'.
So this problem can be solved with $O(n)$ lookups using pretty much any general reachability algorithm.