3
$\begingroup$

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?

$\endgroup$

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.