Optimally Extending Bistandard Graphs on the Orthogonal Grid

In this paper, we provide a linear time algorithm that, given in input an embedding of an n-vertex bistandard graph, produces in output a 2-extension, when it exists, a 3-extension otherwise. This result is the best possible according to known theoretical results. The quality of the produced extension is almost optimal, since the area it requires and the total number of bends it uses approach the lower bounds.

PS Files

Conference Version