On the Hardness of Point-Set Embeddability

DOI10.1007/978-3-642-28076-4_16zbMath1351.68198OpenAlexW2288073247MaRDI QIDQ2889908

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (6)

Positive planar satisfiability problems under 3-connectivity constraints ⋮ Bottleneck Convex Subsets: Finding k Large Convex Sets in a Point Set ⋮ Bottleneck convex subsets: finding \(k\) large convex sets in a point set ⋮ Universal point sets for planar three-trees ⋮ Plane 3-Trees: Embeddability and Approximation ⋮ THE POINT-SET EMBEDDABILITY PROBLEM FOR PLANE GRAPHS

This page was built for publication: On the Hardness of Point-Set Embeddability