On the hardness of point-set embeddability (extended abstract)

DOI10.1007/978-3-642-28076-4_16MaRDI QIDQ2889908zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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)

Recommendations

• The point-set embeddability problem for plane graphs
• The point-set embeddability problem for plane graphs
• Point-set embeddings of plane 3-trees
• Point-set embeddings of plane 3-trees (extended abstract)
• Embedding plane 3-trees in \(\mathbb R^{2}\) and \(\mathbb R^{3}\)

Cited in

(14)

• Positive planar satisfiability problems under 3-connectivity constraints
• Plane 3-trees: embeddability and approximation
• Embedding plane 3-trees in \(\mathbb R^{2}\) and \(\mathbb R^{3}\)
• Automata, Languages and Programming
• The point-set embeddability problem for plane graphs
• Constrained point-set embeddability of planar graphs
• A divide-and-conquer strategy for embedding a distance-net point set into \(E^ n\) and its application
• Upward Point-Set Embeddability
• The point-set embeddability problem for plane graphs
• Bottleneck Convex Subsets: Finding k Large Convex Sets in a Point Set
• Universal point sets for planar three-trees
• Planar embeddability of the vertices of a graph using a fixed point set is NP-hard
• On embedding triconnected cubic graphs on point sets
• 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)