Monotone simultaneous embeddings of paths in d dimensions

DOI10.1007/978-3-319-50106-2_42MaRDI QIDQ2961545zbMATH OpenOpenAlexFDO

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

Publication date 21 February 2017

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1608.08791

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Graph representations (geometric and intersection representations, etc.) (05C62)

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

Recommendations

• Monotone simultaneous paths embeddings in \(\mathbb{R}^d\)
• Monotone simultaneous embeddings of upward planar digraphs
• Algorithms and Data Structures
• Colored Simultaneous Geometric Embeddings
• Monotone Drawings of Graphs with Fixed Embedding

Cites work

• Monotone drawings of graphs
• Monotone drawings of graphs with fixed embedding
• Monotone simultaneous embeddings of paths in \(d\) dimensions
• Monotone simultaneous embeddings of upward planar digraphs
• On a tree and a path with no geometric simultaneous embedding
• On monotone drawings of trees
• On simultaneous planar graph embeddings
• Planar and Quasi Planar Simultaneous Geometric Embedding
• Simultaneous Embedding of Planar Graphs with Few Bends
• Straight-line monotone grid drawings of series-parallel graphs
• Strongly monotone drawings of planar graphs
• Suballowable sequences and geometric permutations

Cited in

(6)

• Monotone simultaneous embeddings of upward planar digraphs
• Monotone simultaneous paths embeddings in \(\mathbb{R}^d\)
• Monotone simultaneous embeddings of paths in \(d\) dimensions
• scientific article; zbMATH DE number 6136123 (Why is no real title available?)
• scientific article; zbMATH DE number 5551581 (Why is no real title available?)
• Relating graph thickness to planar layers and bend complexity

This page was built for publication: Monotone simultaneous embeddings of paths in \(d\) dimensions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2961545)