On upward point set embeddability

DOI10.1016/j.comgeo.2012.11.008zbMath1266.05104MaRDI QIDQ1947995

Tamara Mchedlidze, Michael Kaufmann, Antonios Symvonis

Publication date: 29 April 2013

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2012.11.008

zbMATH Keywords

directed trees; 2-convex point sets; outerplanar digraphs; plynomial time; upward planar digraphs; upward planar drawing; upward point; upward point set embedding

Mathematics Subject Classification ID

05C10: Planar graphs; geometric and topological aspects of graph theory

05C85: Graph algorithms (graph-theoretic aspects)

05C20: Directed graphs (digraphs), tournaments

05C62: Graph representations (geometric and intersection representations, etc.)

Related Items

Upward point set embeddings of paths and trees, Computing upward topological book embeddings of upward planar digraphs, THE POINT-SET EMBEDDABILITY PROBLEM FOR PLANE GRAPHS, Upward Point-Set Embeddability, Upward Point Set Embeddability for Convex Point Sets Is in P

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
• Upward Geometric Graph Embeddings into Point Sets
• Upward Point-Set Embeddability
• Upward Point Set Embeddability for Convex Point Sets Is in P
• 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