On the hardness of point-set embeddability (extended abstract)
DOI10.1007/978-3-642-28076-4_16zbMATH Open1351.68198OpenAlexW2288073247MaRDI QIDQ2889908FDOQ2889908
Authors: Stephane Durocher, Debajyoti Mondal 
Publication date: 8 June 2012
Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-28076-4_16
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Cited In (14)
- Universal point sets for planar three-trees
- The point-set embeddability problem for plane graphs
- Planar embeddability of the vertices of a graph using a fixed point set is NP-hard
- Constrained point-set embeddability of planar graphs
- Automata, Languages and Programming
- Positive planar satisfiability problems under 3-connectivity constraints
- Embedding plane 3-trees in \(\mathbb R^{2}\) and \(\mathbb R^{3}\)
- Upward Point-Set Embeddability
- The point-set embeddability problem for plane graphs
- A divide-and-conquer strategy for embedding a distance-net point set into \(E^ n\) and its application
- Bottleneck convex subsets: finding \(k\) large convex sets in a point set
- On embedding triconnected cubic graphs on point sets
- Plane 3-trees: embeddability and approximation
- Bottleneck Convex Subsets: Finding k Large Convex Sets in a Point Set
This page was built for publication: On the hardness of point-set embeddability (extended abstract)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2889908)
