Algorithms and Bounds for Drawing Non-planar Graphs with Crossing-free Subgraphs
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 Γ of G in the plane such that the edges of...