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

David Bremner 1 Olivier Devillers 2 Marc Glisse 3 Sylvain Lazard 2 Giuseppe Liotta 4 Tamara Mchedlidze 5 Sue Whitesides 6 Stephen Wismath 7
1 Faculty of Computer Science
2 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
3 DATASHAPE - Understanding the Shape of Data
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
4 School of Computing
5 Institute of Theoretical Informatics
6 UVic - Department of Computer Science
7 Department of Mathematics and Computer Science
Abstract : 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.
Type de document :
Communication dans un congrès
24th International Symposium on Graph Drawing & Network Visualization, Sep 2016, Athens, Greece. Springer, Lecture Notes in Computer Science, 9801, Proceedings of 24th International Symposium on Graph Drawing & Network Visualization. <http://algo.math.ntua.gr/~gd2016/>
Liste complète des métadonnées

https://hal.inria.fr/hal-01366148
Contributeur : Olivier Devillers <>
Soumis le : mercredi 14 septembre 2016 - 10:37:17
Dernière modification le : samedi 18 février 2017 - 01:14:35
Document(s) archivé(s) le : jeudi 15 décembre 2016 - 14:36:29

Fichier

simultaneous-paths-embedding.p...
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01366148, version 1
  • ARXIV : 1608.08791

Collections

INRIA | UNIV-LORRAINE | LORIA-ALGO | LORIA | UNIV-PARIS-SACLAY

Citation

David Bremner, Olivier Devillers, Marc Glisse, Sylvain Lazard, Giuseppe Liotta, et al.. Monotone Simultaneous Paths Embeddings in $\mathbb{R}^d$. 24th International Symposium on Graph Drawing & Network Visualization, Sep 2016, Athens, Greece. Springer, Lecture Notes in Computer Science, 9801, Proceedings of 24th International Symposium on Graph Drawing & Network Visualization. <http://algo.math.ntua.gr/~gd2016/>. <hal-01366148>

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de
la notice

296

Téléchargements du document

56

Contact


archive-ouverte@inria.fr