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 Department of Computer Science [Victoria]
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

Littérature citée [14 références]  Voir  Masquer  Télécharger

vignette.png
vignette.png
https://hal.inria.fr/hal-01366148
Contributeur : Olivier Devillers <>
Soumis le : mercredi 14 septembre 2016 - 10:37:17
Dernière modification le : jeudi 8 novembre 2018 - 10:58:32

Fichiers

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

Identifiants

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

Collections

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

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

461

Téléchargements de fichiers

95

Contact


archive-ouverte@inria.fr