Inserting Multiple Edges into a Planar Graph

Markus Chimani, Petr Hliněný

Let $G$ be a connected planar (but not yet embedded) graph and $F$ a set of additional edges not yet in $G$. The {multiple edge insertion} problem (MEI) asks for a drawing of $G+F$…