Publication at Faculty of Mathematics and Physics |
2010
Abstract
We present a linear time algorithm for deciding if a planar embedding of a part of graph can be extended to a noncrossing embedding of the entire graph. We further who that several optimization extensions of this problem are NP-complete.