# Convert DAG whose transitive reduction is non-planar to a planar DAG with same transitive closure

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:

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?