Upward Point Set Embeddability for Convex Point Sets Is in P

DOI10.1007/978-3-642-25878-7_38zbMath1312.05133arXiv1108.3092OpenAlexW1502386414MaRDI QIDQ3223972

Michael Kaufmann, Tamara Mchedlidze, Antonios Symvonis

Publication date: 9 March 2012

Published in: Graph Drawing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items (3)

Upward planar embedding of an \(n\)-vertex oriented path on \(O(n^2)\) points ⋮ Reprint of: ``Upward planar embedding of an \(n\)-vertex oriented path on \(O(n^2)\) points ⋮ On upward point set embeddability

Cites Work

• Drawing colored graphs on colored points
• Upward straight-line embeddings of directed graphs into point sets
• On the thickness of graphs of given degree
• On embedding an outer-planar graph in a point set
• On upward point set embeddability
• Upward Geometric Graph Embeddings into Point Sets
• Upward Point-Set Embeddability
• Embeddability Problems for Upward Planar Digraphs
• Stack and Queue Layouts of Directed Acyclic Graphs: Part I
• Optimal Algorithms to Embed Trees in a Point Set
• Embedding Vertices at Points: Few Bends Suffice for Planar Graphs
• Planar embeddability of the vertices of a graph using a fixed point set is NP-hard
• k-colored Point-set Embeddability of Outerplanar Graphs
• Computing Upward Topological Book Embeddings of Upward Planar Digraphs
• Embedding planar graphs at fixed vertex locations

This page was built for publication: Upward Point Set Embeddability for Convex Point Sets Is in P