David Bremner ; Olivier Devillers ; Marc Glisse ; Sylvain Lazard ; Giuseppe Liotta et al. - Monotone Simultaneous Paths Embeddings in $\mathbb{R}^d$

dmtcs:3692 - Discrete Mathematics & Theoretical Computer Science, January 5, 2018, Vol. 20 no. 1 - https://doi.org/10.23638/DMTCS-20-1-1
Monotone Simultaneous Paths Embeddings in $\mathbb{R}^d$

Authors: David Bremner ; Olivier Devillers ; Marc Glisse ; Sylvain Lazard ; Giuseppe Liotta ; Tamara Mchedlidze ; Guillaume Moroz ; Sue Whitesides ; Stephen Wismath

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.


Volume: Vol. 20 no. 1
Section: Discrete Algorithms
Published on: January 5, 2018
Accepted on: January 5, 2018
Submitted on: May 31, 2017
Keywords: point hyperplane duality,graph drawing,high-dimensional space,algorithm,[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG]


Share

Consultation statistics

This page has been seen 1015 times.
This article's PDF has been downloaded 457 times.