8.7CGMar 10
Simultaneous Embedding of Two Paths on the GridStephen Kobourov, William Lenhart, Giuseppe Liotta et al.
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.