Point-Set Embedding in Three Dimensions Henk Meijer and Stephen Wismath Vol. 19, no. 1, pp. 243-257, 2015. Concise paper. Abstract Given a graph $G$ with $n$ vertices and $m$ edges, and a set $P$ of $n$ points on a three-dimensional integer grid, the 3D Point-Set Embeddability problem is to determine a (three-dimensional) crossing-free drawing of $G$ with vertices located at $P$ and with edges drawn as poly-lines with bend-points at integer grid points. We solve a variant of the problem in which the points of $P$ lie on a plane. The resulting drawing lies in a bounding box of reasonable volume and uses at most $O(\log m)$ bends per edge. If a particular point-set $P$ is not specified, we show that the graph $G$ can be drawn crossing-free with at most $O(\log m)$ bends per edge in a volume bounded by $O((n+m) \log m)$. Our construction is asymptotically similar to previously known drawings, however avoids a possibly non-polynomial preprocessing step. Submitted: July 2013. Reviewed: April 2015. Accepted: April 2015. Final: April 2015. Published: May 2015. Communicated by Prosenjit K. Bose article (PDF) BibTeX