Monotone Simultaneous Paths Embeddings in $\mathbb{R}^d$
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...
| Main Authors: | , , , , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2018-01-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/3692/pdf |
| _version_ | 1827323729138417664 |
|---|---|
| author | David Bremner Olivier Devillers Marc Glisse Sylvain Lazard Giuseppe Liotta Tamara Mchedlidze Guillaume Moroz Sue Whitesides Stephen Wismath |
| author_facet | David Bremner Olivier Devillers Marc Glisse Sylvain Lazard Giuseppe Liotta Tamara Mchedlidze Guillaume Moroz Sue Whitesides Stephen Wismath |
| author_sort | David Bremner |
| collection | DOAJ |
| 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. |
| first_indexed | 2024-04-25T01:58:13Z |
| format | Article |
| id | doaj.art-1f4a2e4cfbb64ff8bb658423c8c7f995 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:58:13Z |
| publishDate | 2018-01-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-1f4a2e4cfbb64ff8bb658423c8c7f9952024-03-07T15:36:36ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502018-01-01Vol. 20 no. 1Discrete Algorithms10.23638/DMTCS-20-1-13692Monotone Simultaneous Paths Embeddings in $\mathbb{R}^d$David Bremner0Olivier Devillers1https://orcid.org/0000-0003-4275-5068Marc Glisse2https://orcid.org/0000-0001-6914-1651Sylvain Lazard3Giuseppe Liotta4Tamara Mchedlidze5Guillaume Moroz6Sue Whitesides7Stephen Wismath8Faculty of Computer ScienceGeometric Algorithms and Models Beyond the Linear and Euclidean realmUnderstanding the Shape of DataGeometric Algorithms and Models Beyond the Linear and Euclidean realmDipartimento di Matematica e Informatica [Perugia]Institute of Theoretical InformaticsGeometric Algorithms and Models Beyond the Linear and Euclidean realmDepartment of Computer Science [Victoria]Department of Mathematics and Computer ScienceWe 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.https://dmtcs.episciences.org/3692/pdfpoint hyperplane dualitygraph drawinghigh-dimensional spacealgorithm[info.info-cg] computer science [cs]/computational geometry [cs.cg] |
| spellingShingle | David Bremner Olivier Devillers Marc Glisse Sylvain Lazard Giuseppe Liotta Tamara Mchedlidze Guillaume Moroz Sue Whitesides Stephen Wismath Monotone Simultaneous Paths Embeddings in $\mathbb{R}^d$ Discrete Mathematics & Theoretical Computer Science point hyperplane duality graph drawing high-dimensional space algorithm [info.info-cg] computer science [cs]/computational geometry [cs.cg] |
| title | Monotone Simultaneous Paths Embeddings in $\mathbb{R}^d$ |
| title_full | Monotone Simultaneous Paths Embeddings in $\mathbb{R}^d$ |
| title_fullStr | Monotone Simultaneous Paths Embeddings in $\mathbb{R}^d$ |
| title_full_unstemmed | Monotone Simultaneous Paths Embeddings in $\mathbb{R}^d$ |
| title_short | Monotone Simultaneous Paths Embeddings in $\mathbb{R}^d$ |
| title_sort | monotone simultaneous paths embeddings in mathbb r d |
| topic | point hyperplane duality graph drawing high-dimensional space algorithm [info.info-cg] computer science [cs]/computational geometry [cs.cg] |
| url | https://dmtcs.episciences.org/3692/pdf |
| work_keys_str_mv | AT davidbremner monotonesimultaneouspathsembeddingsinmathbbrd AT olivierdevillers monotonesimultaneouspathsembeddingsinmathbbrd AT marcglisse monotonesimultaneouspathsembeddingsinmathbbrd AT sylvainlazard monotonesimultaneouspathsembeddingsinmathbbrd AT giuseppeliotta monotonesimultaneouspathsembeddingsinmathbbrd AT tamaramchedlidze monotonesimultaneouspathsembeddingsinmathbbrd AT guillaumemoroz monotonesimultaneouspathsembeddingsinmathbbrd AT suewhitesides monotonesimultaneouspathsembeddingsinmathbbrd AT stephenwismath monotonesimultaneouspathsembeddingsinmathbbrd |