Monotone Simultaneous Paths Embeddings in $\mathbb{R}^d$

David Bremner (1) , Olivier Devillers (2) , Marc Glisse (3) , Sylvain Lazard (2) , Giuseppe Liotta (4) , Tamara Mchedlidze (5) , Sue Whitesides (6) , Stephen Wismath (7)

1 Faculty of Computer Science
2 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
3 DATASHAPE - Understanding the Shape of Data
4 School of Computing
5 Institute of Theoretical Informatics
6 Department of Computer Science [Victoria]
7 Department of Mathematics and Computer Science

We study the following problem: Given $k$ paths that share the same vertex set, is there a simultaneous geometric embedding of these paths such that each individual drawing is monotone in some direction? We prove that for any dimension $d\geq 2$, there is a set of $d + 1$ paths that does not admit a monotone simultaneous geometric embedding.

Domaines: Géométrie algorithmique [cs.CG]

David Bremner, Olivier Devillers, Marc Glisse, Sylvain Lazard, Giuseppe Liotta, et al.. Monotone Simultaneous Paths Embeddings in $\mathbb{R}^d$. 24th International Symposium on Graph Drawing & Network Visualization, Sep 2016, Athens, Greece. ⟨10.1007/978-3-319-50106-2_42⟩. ⟨hal-01366148⟩