# Edge removal to convert a non-planar DAG to a planar DAG while maintaining reachability?

Is there an algorithm that removes edges to convert a non-planar DAG to a planar DAG while maintaining reachability? For example, the graph $G$ below is non-planar:

but, by removing certain edges to produce $G'$, it can be made planar but every vertex still has the same transitive closure (meaning vertex $t$ is reachable form vertex $s$ in $G'$ iff the same is true in $G$)

Is there an algorithm to do this for any general DAG (or return an error if it's not possible)?

My use case is that I'd like to use Thorup's algorithm for reachability, but it only works on planar graphs.

## 1 Answer

Yes, there's a nice algorithm for this. Compute the transitive reduction, then check whether the result is planar.

Why does this work? The transitive reduction is the graph with the smallest number of edges, that has the same reachability relationships as the original graph. It is also unique. Moreover, any other graph with the same reachability relationships must include all the edges in the transitive reduction (plus possibly some others). Thus, if the transitive reduction isn't planar, no other graph with the same reachability relationship will be planar (as adding more edges to a non-planar graph can never make it planar).