 |
Discrete Mathematics & Theoretical Computer Science |
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-1Monotone Simultaneous Paths Embeddings in $\mathbb{R}^d$Article
Authors: David Bremner 1; Olivier Devillers 
2; Marc Glisse 3; Sylvain Lazard 2; Giuseppe Liotta 4; Tamara Mchedlidze 5; Guillaume Moroz 2; Sue Whitesides 6; Stephen Wismath 7
- 1 Faculty of Computer Science
- 2 Geometric Algorithms and Models Beyond the Linear and Euclidean realm [GAMBLE]
- 3 Understanding the Shape of Data [DATASHAPE]
- 4 Dipartimento di Matematica e Informatica [Perugia]
- 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.
Source: HAL:hal-01529154v2
Volume: Vol. 20 no. 1
Section: Discrete Algorithms
Published on: January 5, 2018
Accepted on: December 1, 2017
Submitted on: May 31, 2017
Keywords: [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], [en] point hyperplane duality, graph drawing, high-dimensional space, algorithm
Funding:
- Source : OpenAIRE Graph
- Funder: Natural Sciences and Engineering Research Council of Canada
Consultation statistics
This page has been seen 1525 times.
This article's PDF has been downloaded 735 times.