Home  Issues  Aims and Scope  Instructions for Authors 
DOI: 10.7155/jgaa.00355
PointSet Embedding in Three Dimensions
Henk Meijer and
Stephen Wismath
Vol. 19, no. 1, pp. 243257, 2015. Concise paper.
Abstract Given a graph $G$ with $n$ vertices and $m$ edges, and a set $P$ of $n$ points on a threedimensional integer grid,
the 3D PointSet Embeddability problem is to determine a (threedimensional) crossingfree drawing of $G$
with vertices located at $P$ and with edges drawn as polylines with bendpoints 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 pointset $P$ is not specified, we show that the graph $G$ can be drawn crossingfree 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 nonpolynomial preprocessing step.

Submitted: July 2013.
Reviewed: April 2015.
Accepted: April 2015.
Final: April 2015.
Published: May 2015.
Communicated by
Prosenjit K. Bose
