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