Monotone simultaneous embeddings of paths in d dimensions

DOI10.1007/978-3-319-50106-2_42zbMATH Open1478.68220arXiv1608.08791OpenAlexW2560321580MaRDI QIDQ2961545FDOQ2961545

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)

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.

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

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

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)

Cites Work

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

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
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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)