The point-set embeddability problem for plane graphs

DOI10.1145/2261250.2261257MaRDI QIDQ2874563zbMATH OpenOpenAlexFDO

Authors Martin Vatshelle, Therese Biedl

Publication date 7 August 2014

Published in Proceedings of the twenty-eighth annual symposium on Computational geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2261250.2261257

zbMATH Keywords

carving widthgraph drawingpoint-set embedding

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Connectivity (05C40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The point-set embeddability problem for plane graphs
• On the hardness of point-set embeddability (extended abstract)
• Planar embeddability of the vertices of a graph using a fixed point set is NP-hard
• Point-set embeddings of plane 3-trees
• Point-set embeddings of plane 3-trees (extended abstract)

Cited in

(28)

• Inapproximability of rank, clique, Boolean, and maximum induced matching-widths under small set expansion hypothesis
• Mim-width. I. Induced path problems
• List k-colouring P_t-free graphs: a mim-width perspective
• Mim-width. III. Graph powers and generalized distance domination problems
• Optimal point-set embedding of wheel graphs and a sub-class of 3-trees
• Lower bounds on the mim-width of some graph classes
• On algorithmic applications of sim-width and mim-width of (H₁,H₂)-free graphs
• The point-set embeddability problem for plane graphs
• On the hardness of point-set embeddability (extended abstract)
• Graphs embedded in the plane with a bounded number of accumulation points
• Kinetic and Stationary Point-Set Embeddability for Plane Graphs
• Generalized distance domination problems and their complexity on graphs of bounded mim-width
• More applications of the d-neighbor equivalence: connectivity and acyclicity constraints
• Reducing the domination number of graphs via edge contractions
• Polynomial-time algorithms for the longest induced path and induced disjoint paths problems on graphs of bounded mim-width
• Plane 3-trees: embeddability and approximation
• EMBEDDING POINT SETS INTO PLANE GRAPHS OF SMALL DILATION
• Planar embeddability of the vertices of a graph using a fixed point set is NP-hard
• The perfect matching cut problem revisited
• Bounding the Mim-Width of Hereditary Graph Classes.
• Branchwidth is \((1, g)\)-self-dual
• Excluding a planar matching minor in bipartite graphs
• Upward pointset embeddings of planar st-graphs
• Comparing width parameters on graph classes
• Upward pointset embeddings of planar \(st\)-graphs
• Braces of perfect matching width 2
• On the thinness of trees
• Tangling and untangling trees on point-sets

This page was built for publication: The point-set embeddability problem for plane graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2874563)