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

Abstract

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.

Keywords

• point hyperplane duality
• graph drawing
• high-dimensional space
• algorithm
• [info.info-cg] computer science [cs]/computational geometry [cs.cg]