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$Article

Authors: David Bremner 1; Olivier Devillers ORCID2; Marc Glisse ORCID3; 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
  • 3 Understanding the Shape of Data
  • 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.

https://doi.org/10.23638/DMTCS-20-1-1
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: point hyperplane duality,graph drawing,high-dimensional space,algorithm,[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG]
Funding:
    Source : OpenAIRE Graph
  • Funder: Natural Sciences and Engineering Research Council of Canada

Share and export

Consultation statistics

This page has been seen 1256 times.
This article's PDF has been downloaded 574 times.