The point-set embeddability problem for plane graphs

DOI10.1145/2261250.2261257zbMath1293.05060OpenAlexW2011729204MaRDI QIDQ2874563

Martin Vatshelle, Therese C. 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

graph drawingpoint-set embeddingcarving width

Mathematics Subject Classification ID

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

Related Items (16)

Optimal point-set embedding of wheel graphs and a sub-class of 3-trees ⋮ Mim-width. I. Induced path problems ⋮ Lower bounds on the mim-width of some graph classes ⋮ Branchwidth is \((1, g)\)-self-dual ⋮ Excluding a planar matching minor in bipartite graphs ⋮ Unnamed Item ⋮ On algorithmic applications of sim-width and mim-width of \((H_1,H_2)\)-free graphs ⋮ Inapproximability of rank, clique, Boolean, and maximum induced matching-widths under small set expansion hypothesis ⋮ List \(k\)-colouring \(P_t\)-free graphs: a mim-width perspective ⋮ Bounding the Mim-Width of Hereditary Graph Classes. ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The perfect matching cut problem revisited ⋮ Mim-width. III. Graph powers and generalized distance domination problems ⋮ Plane 3-Trees: Embeddability and Approximation

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