Monotone Simultaneous Embedding of Directed Paths

O. Aichholzer, T. Hackl, S. Lutteropp, T. Mchedlidze, A. Pilz, and B. Vogtenhuber

Abstract:

We consider a variant of monotone simultaneous embeddings (MSEs) of directed graphs where all graphs are directed paths and have distinct directions of monotonicity. In contrast to the known result that any two directed paths admit an MSE, there exist examples of three paths that do not admit such an embedding for any possible choice of directions of monotonicity. We prove that if an MSE of three paths exists then it also exists for any possible choice of directions of monotonicity. We provide a polynomial-time algorithm that, given three paths, decides whether an MSE exists. Finally, we provide a polynomial-time algorithm that answers the existence question for any given number of paths and predefined directions of monotonicity.

Reference: O. Aichholzer, T. Hackl, S. Lutteropp, T. Mchedlidze, A. Pilz, and B. Vogtenhuber. Monotone simultaneous embedding of directed paths. In Proc. $30^{th}$ European Workshop on Computational Geometry EuroCG '14, page online, Dead Sea, Israel, 2014.