Upward point set embeddability for convex point sets is in P

DOI10.1007/978-3-642-25878-7_38MaRDI QIDQ3223972zbMATH OpenOpenAlexFDO

Authors 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

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

Abstract: In this paper, we present a polynomial dynamic programming algorithm that tests whether a $n$-vertex directed tree $T$ has an upward planar embedding into a convex point-set $S$ of size $n$. Further, we extend our approach to the class of outerplanar digraphs. This nontrivial and surprising result implies that any given digraph can be efficiently tested for an upward planar embedding into a given convex point set.

Recommendations

• On upward point set embeddability
• Upward Point-Set Embeddability
• Upward Straight-Line Embeddings of Directed Graphs into Point Sets
• Upward straight-line embeddings of directed graphs into point sets
• Upward geometric graph embeddings into point sets

Cites work

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

Cited in

(10)

• Upward straight-line embeddings of directed graphs into point sets
• On upward point set embeddability
• An SPQR-tree-like embedding representation for upward planarity
• Upward planar embedding of an \(n\)-vertex oriented path on \(O(n^2)\) points
• Upward geometric graph embeddings into point sets
• Upward Point-Set Embeddability
• Reprint of: ``Upward planar embedding of an \(n\)-vertex oriented path on \(O(n^2)\) points
• Upward Straight-Line Embeddings of Directed Graphs into Point Sets
• Upward pointset embeddings of planar st-graphs
• Upward pointset embeddings of planar \(st\)-graphs

This page was built for publication: Upward point set embeddability for convex point sets is in P

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