On upward point set embeddability

DOI10.1016/j.comgeo.2012.11.008zbMath1266.05104OpenAlexW2158531399MaRDI 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 trees2-convex point setsouterplanar digraphsplynomial timeupward planar digraphsupward planar drawingupward pointupward point set embedding

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (5)

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

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

This page was built for publication: On upward point set embeddability