Monotone simultaneous embeddings of paths in d dimensions

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

doi:10.1007/978-3-319-50106-2_42

Monotone simultaneous embeddings of paths in d dimensions

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

École Polytechnique

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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, there is a set of d + 1 paths that does not admit a monotone simultaneous geometric embedding.

Original language	English
Title of host publication	Graph Drawing and Network Visualization - 24th International Symposium, GD 2016, Revised Selected Papers
Editors	Martin Nollenburg, Yifan Hu
Publisher	Springer Verlag
Pages	546-553
Number of pages	8
ISBN (Print)	9783319501055
DOIs	https://doi.org/10.1007/978-3-319-50106-2_42
Publication status	Published - 1 Jan 2016
Event	24th International Symposium on Graph Drawing and Network Visualization, GD 2016 - Athens, Greece Duration: 19 Sept 2016 → 21 Sept 2016

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9801 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	24th International Symposium on Graph Drawing and Network Visualization, GD 2016
Country/Territory	Greece
City	Athens
Period	19/09/16 → 21/09/16

Access to Document

10.1007/978-3-319-50106-2_42

Cite this

Bremner, D., Devillers, O., Glisse, M., Lazard, S., Liotta, G., Mchedlidze, T., Whitesides, S., & Wismath, S. (2016). Monotone simultaneous embeddings of paths in d dimensions. In M. Nollenburg, & Y. Hu (Eds.), Graph Drawing and Network Visualization - 24th International Symposium, GD 2016, Revised Selected Papers (pp. 546-553). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9801 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-50106-2_42

Bremner, David ; Devillers, Olivier ; Glisse, Marc et al. / Monotone simultaneous embeddings of paths in d dimensions. Graph Drawing and Network Visualization - 24th International Symposium, GD 2016, Revised Selected Papers. editor / Martin Nollenburg ; Yifan Hu. Springer Verlag, 2016. pp. 546-553 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{8da8a5ac47d1456e93cb8e7e4fd2a2dc,

title = "Monotone simultaneous embeddings of paths in d dimensions",

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, there is a set of d + 1 paths that does not admit a monotone simultaneous geometric embedding.",

author = "David Bremner and Olivier Devillers and Marc Glisse and Sylvain Lazard and Giuseppe Liotta and Tamara Mchedlidze and Sue Whitesides and Stephen Wismath",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG 2016.; 24th International Symposium on Graph Drawing and Network Visualization, GD 2016 ; Conference date: 19-09-2016 Through 21-09-2016",

year = "2016",

month = jan,

day = "1",

doi = "10.1007/978-3-319-50106-2\_42",

language = "English",

isbn = "9783319501055",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "546--553",

editor = "Martin Nollenburg and Yifan Hu",

booktitle = "Graph Drawing and Network Visualization - 24th International Symposium, GD 2016, Revised Selected Papers",

}

Bremner, D, Devillers, O, Glisse, M, Lazard, S, Liotta, G, Mchedlidze, T, Whitesides, S & Wismath, S 2016, Monotone simultaneous embeddings of paths in d dimensions. in M Nollenburg & Y Hu (eds), Graph Drawing and Network Visualization - 24th International Symposium, GD 2016, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9801 LNCS, Springer Verlag, pp. 546-553, 24th International Symposium on Graph Drawing and Network Visualization, GD 2016, Athens, Greece, 19/09/16. https://doi.org/10.1007/978-3-319-50106-2_42

Monotone simultaneous embeddings of paths in d dimensions. / Bremner, David; Devillers, Olivier; Glisse, Marc et al.
Graph Drawing and Network Visualization - 24th International Symposium, GD 2016, Revised Selected Papers. ed. / Martin Nollenburg; Yifan Hu. Springer Verlag, 2016. p. 546-553 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9801 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Monotone simultaneous embeddings of paths in d dimensions

AU - Bremner, David

AU - Devillers, Olivier

AU - Glisse, Marc

AU - Lazard, Sylvain

AU - Liotta, Giuseppe

AU - Mchedlidze, Tamara

AU - Whitesides, Sue

AU - Wismath, Stephen

PY - 2016/1/1

Y1 - 2016/1/1

N2 - 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, there is a set of d + 1 paths that does not admit a monotone simultaneous geometric embedding.

AB - 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, there is a set of d + 1 paths that does not admit a monotone simultaneous geometric embedding.

U2 - 10.1007/978-3-319-50106-2_42

DO - 10.1007/978-3-319-50106-2_42

M3 - Conference contribution

AN - SCOPUS:85007303063

SN - 9783319501055

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 546

EP - 553

BT - Graph Drawing and Network Visualization - 24th International Symposium, GD 2016, Revised Selected Papers

A2 - Nollenburg, Martin

A2 - Hu, Yifan

PB - Springer Verlag

T2 - 24th International Symposium on Graph Drawing and Network Visualization, GD 2016

Y2 - 19 September 2016 through 21 September 2016

ER -

Bremner D, Devillers O, Glisse M, Lazard S, Liotta G, Mchedlidze T et al. Monotone simultaneous embeddings of paths in d dimensions. In Nollenburg M, Hu Y, editors, Graph Drawing and Network Visualization - 24th International Symposium, GD 2016, Revised Selected Papers. Springer Verlag. 2016. p. 546-553. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-50106-2_42

Monotone simultaneous embeddings of paths in d dimensions

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this