Planar embeddability of the vertices of a graph using a fixed point set is NP-hard
From MaRDI portal
Publication:5301397
DOI10.7155/JGAA.00132zbMATH Open1161.68645OpenAlexW2122264000MaRDI QIDQ5301397FDOQ5301397
Authors: S. Cabello 
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
Recommendations
- The point-set embeddability problem for plane graphs
- The point-set embeddability problem for plane graphs
- On the hardness of point-set embeddability (extended abstract)
- Minimum Length Embedding of Planar Graphs at Fixed Vertex Locations
- Planar straight-line point-set embedding of trees with partial embeddings
Cited In (30)
- A Note on Universal Point Sets for Planar Graphs
- Upward straight-line embeddings of directed graphs into point sets
- Universal point sets for planar three-trees
- Orthogeodesic point-set embedding of trees
- Point-set embeddings of plane \(3\)-trees
- Minimal Representations of Order Types by Geometric Graphs
- Planar subgraphs without low-degree nodes
- Small universal point sets for \(k\)-outerplanar graphs
- Minimal representations of order types by geometric graphs
- The Planar k-Means Problem is NP-Hard
- On upward point set embeddability
- Upward point set embeddings of paths and trees
- A note on universal point sets for planar graphs
- Plane 3-Trees: Embeddability and Approximation
- Upward Point-Set Embeddability
- Small Point Sets for Simply-Nested Planar Graphs
- Improved Bounds for Drawing Trees on Fixed Points with L-Shaped Edges
- Upward Point Set Embeddability for Convex Point Sets Is in P
- Planar straight-line point-set embedding of trees with partial embeddings
- Constrained Point Set Embedding of a Balanced Binary Tree
- Optimal point-set embedding of wheel graphs and a sub-class of 3-trees
- The point-set embeddability problem for plane graphs
- Curve-constrained drawings of planar graphs
- Point-set embeddings of trees with given partial drawings
- Improved algorithms for the point-set embeddability problem for plane 3-trees
- Orthogeodesic Point-Set Embedding of Trees
- Embedding Plane 3-Trees in ℝ2 and ℝ3
- On 1-bend upward point-set embeddings of \(st\)-digraphs
- Geometry and Generation of a New Graph Planarity Game
- Upward Straight-Line Embeddings of Directed Graphs into Point Sets
This page was built for publication: Planar embeddability of the vertices of a graph using a fixed point set is NP-hard
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5301397)
