Algorithms and Bounds for Drawing Non-planar Graphs with Crossing-free Subgraphs

Patrizio Angelini, Carla Binucci, Giordano Da Lozzo +5

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…