Simultaneous Embedding of Two Paths on the Grid

Authors: Stephen Kobourov, William Lenhart, Giuseppe Liotta, Daniel Perz, Pavel Valtr, Johannes Zink

We study the problem of simultaneous geometric embedding of two paths without self-intersections on an integer grid. We show that minimizing the length of the longest edge of such an embedding is NP-hard. We also show that we can minimize in $O(n^{3/2})$ time the perimeter of an integer grid containing such an embedding if one path is $x$-monotone and the other is $y$-monotone.