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

DOI : 10.23638/DMTCS-20-1-1

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]

This page has been seen 369 times.

This article's PDF has been downloaded 132 times.