Simultaneous Embedding of Two Paths on the Grid

Simultaneous geometric embedding of graphs on an integer grid is a classical research topic in Graph Drawing. When the graphs are two paths, one can additionally require that one path is x-monotone and the other is y-monotone (the monotone setting). A simple and elegant algorithm is known to simultaneously embed two paths on an integer grid in the monotone setting. The resulting embedding is, however, not optimal in terms of grid size or edge lengths. In this paper, we study some quality measures of simultaneous embeddings of two paths on an integer grid, in both the monotone and in the unconstrained setting. In the monotone setting, we present almost-linear time algorithms to minimize either the perimeter of the bounding box or the sum of the edge lengths in the $L_1$-norm. Both results are based on transforming the problem into that of finding a minimum vertex cover (weighted for the $L_1$-norm problem) on a related bipartite graph derived from the two paths. As for the unconstrained setting, we show that both minimizing the length of the longest edge and minimizing the sum of the edge lengths of a simultaneous embedding of two paths on an integer grid is NP-hard.