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

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

Others:: Faculty of Computer Science ; University of New Brunswick (UNB); Geometric Algorithms and Models Beyond the Linear and Euclidean realm (GAMBLE ) ; 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); Dipartimento di Matematica e Informatica [Perugia] (DMI) ; 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