An algorithm for extending partial planar drawings

This thesis studies the problem of partially embedded planarity. The input of the problem is a graph G and a planar drawing of a subgraph of G. The goal is to decide whether the drawing of the subgraph can be extended to a planar drawing of the entire graph G. It has already been proved that the partially embedded planarity problem can be solved in linear time. However, all known linear algorithms are relatively complicated. This is probably the reason that no implementation has yet been published. We will introduce a new, simpler linear algorithm that solves the problem and we will prove its correctness. Next, we will enclose an implementation of this algorithm in the C++ programming language.