For any non-planar DAG, we can compute the transitive reduction, and sometimes it will be planar (e.g. $K_5$).

However, sometimes the transitive reduction is also non-planar. For example, $K_{3, 3}$'s transitive reduction is just $K_{3, 3}$.

Alternatively, it's possible to add vertices and adjust the edges to maintain the same transitive closure as $K_{3,3}$, while producing a planar graph:

enter image description here

Here $U_{i}$ means "utility i" and $H_i$ means "house i", as per the Three Utilities Problem.

Is there an algorithm that can accomplish this for a general DAG, so that the resulting graph is planar and can be used with Thorup's algorithm?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.