Planar embeddability of the vertices of a graph using a fixed point set is NP-hard
From MaRDI portal
Publication:5301397
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
(36)- Constrained point set embedding of a balanced binary tree
- On computational complexity of length embeddability of graphs
- Upward Straight-Line Embeddings of Directed Graphs into Point Sets
- A Note on Universal Point Sets for Planar Graphs
- Improved bounds for drawing trees on fixed points with L-shaped edges
- Upward straight-line embeddings of directed graphs into point sets
- Universal point sets for planar three-trees
- Upward pointset embeddings of planar \(st\)-graphs
- A linear-time approximation algorithm for the minimum-length geometric embedding of trees
- The point-set embeddability problem for plane graphs
- Point-set embeddings of plane 3-trees
- Orthogeodesic point-set embedding of trees
- Small point sets for simply-nested planar graphs
- Minimal Representations of Order Types by Geometric Graphs
- Upward point set embeddability for convex point sets is in P
- Small universal point sets for \(k\)-outerplanar graphs
- Planar subgraphs without low-degree nodes
- Geometry and generation of a new graph planarity game
- Minimal representations of order types by geometric graphs
- On upward point set embeddability
- The Planar k-Means Problem is NP-Hard
- Upward point set embeddings of paths and trees
- Deciding whether a grid is a topological subgraph of a planar graph is NP-complete
- A note on universal point sets for planar graphs
- Embedding plane 3-trees in \(\mathbb R^{2}\) and \(\mathbb R^{3}\)
- Upward Point-Set Embeddability
- Planar straight-line point-set embedding of trees with partial embeddings
- Optimal point-set embedding of wheel graphs and a sub-class of 3-trees
- Orthogeodesic point-set embedding of 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
- Upward pointset embeddings of planar st-graphs
- Plane 3-trees: embeddability and approximation
- On 1-bend upward point-set embeddings of \(st\)-digraphs
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)
