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

Creators: Bremner, David; Devillers, Olivier; Glisse, Marc; Lazard, Sylvain; Liotta, Giuseppe; Mchedlidze, Tamara; Whitesides, Sue; Wismath, Stephen

Others:: Faculty of Computer Science ; University of New Brunswick (UNB); Effective Geometric Algorithms for Surfaces and Visibility (VEGAS) ; Inria Nancy - Grand Est ; Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Algorithms, Computation, Image and Geometry (LORIA - ALGO) ; Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA) ; Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA) ; Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS); Understanding the Shape of Data (DATASHAPE) ; Inria Sophia Antipolis - Méditerranée (CRISAM) ; Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Inria Saclay - Ile de France ; Institut National de Recherche en Informatique et en Automatique (Inria); School of Computing ; Università degli Studi di Perugia = University of Perugia (UNIPG); Institute of Theoretical Informatics ; Karlsruhe Institute of Technology (KIT); Department of Computer Science [Victoria] ; University of Victoria [Canada] (UVIC); Department of Mathematics and Computer Science ; University of Lethbridge

Description

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.

Abstract

International audience

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

Description

Abstract

Additional details