2
$\begingroup$

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:

enter image description here

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$)

enter image description here

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

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).

Improve this answer
$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.