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

dmtcs:4177 - Discrete Mathematics & Theoretical Computer Science, January 5, 2018, Vol. 20 no. 1
Monotone Simultaneous Paths Embeddings in $\mathbb{R}^d$

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

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.


Source : oai:HAL:hal-01529154v2
Volume: Vol. 20 no. 1
Section: Discrete Algorithms
Published 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 265 times.
This article's PDF has been downloaded 108 times.