Planar embeddability of the vertices of a graph using a fixed point set is NP-hard
From MaRDI portal
Publication:5301397
DOI10.7155/jgaa.00132zbMath1161.68645OpenAlexW2122264000MaRDI QIDQ5301397
Publication date: 19 January 2009
Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/55397
Related Items (27)
IMPROVED ALGORITHMS FOR THE POINT-SET EMBEDDABILITY PROBLEM FOR PLANE 3-TREES ⋮ Upward Straight-Line Embeddings of Directed Graphs into Point Sets ⋮ Orthogeodesic point-set embedding of trees ⋮ Optimal point-set embedding of wheel graphs and a sub-class of 3-trees ⋮ Embedding Plane 3-Trees in ℝ2 and ℝ3 ⋮ Orthogeodesic Point-Set Embedding of Trees ⋮ Small Point Sets for Simply-Nested Planar Graphs ⋮ Upward Point Set Embeddability for Convex Point Sets Is in P ⋮ Point-set embeddings of plane \(3\)-trees ⋮ On upward point set embeddability ⋮ A Note on Universal Point Sets for Planar Graphs ⋮ Minimal representations of order types by geometric graphs ⋮ A note on universal point sets for planar graphs ⋮ Point-set embeddings of trees with given partial drawings ⋮ Improved Bounds for Drawing Trees on Fixed Points with L-Shaped Edges ⋮ Minimal Representations of Order Types by Geometric Graphs ⋮ Upward point set embeddings of paths and trees ⋮ Small universal point sets for \(k\)-outerplanar graphs ⋮ Universal point sets for planar three-trees ⋮ Curve-constrained drawings of planar graphs ⋮ Upward Point-Set Embeddability ⋮ Planar straight-line point-set embedding of trees with partial embeddings ⋮ Geometry and Generation of a New Graph Planarity Game ⋮ Upward straight-line embeddings of directed graphs into point sets ⋮ Plane 3-Trees: Embeddability and Approximation ⋮ Constrained Point Set Embedding of a Balanced Binary Tree ⋮ THE POINT-SET EMBEDDABILITY PROBLEM FOR PLANE GRAPHS
This page was built for publication: Planar embeddability of the vertices of a graph using a fixed point set is NP-hard
