Point Set Embedding in 3D
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(logm) 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(logm) bends per edge in a volume bounded by O((n+m) logm). 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)