Drawing Non-Planar Graphs with Crossing-Free Subgraphs

Abstract

We initiate the study of the following problem$:$ Given a non-planar graph $G$ and a planar subgraph $S$ of $G$, does there exist a straight-line drawing $\Gamma$ of $G$ in the plane such that the edges of $S$ are not crossed in $\Gamma$? We give positive and negative results for different kinds of spanning subgraphs $S$ of $G$. Moreover, in order to enlarge the subset of instances that admit a solution, we consider the possibility of bending the edges of $G \setminus S$; in this setting different trade-offs between number of bends and drawing area are given.