Simultaneous Embedding of Two Paths on the Grid
This addresses computational geometry challenges for graph drawing and layout optimization, with incremental algorithmic improvements for specific cases.
The paper tackles the problem of embedding two non-intersecting paths on an integer grid, proving that minimizing the longest edge length is NP-hard and providing an O(n^{3/2}) algorithm to minimize the perimeter when one path is x-monotone and the other is y-monotone.
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.