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?
