Algorithms and bounds for drawing non-planar graphs with crossing-free subgraphs (Q904086)

In this paper, the authors 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 \(\Gamma\) of \(G\) in the plane such that the edges of \(S\) are not crossed in \(\Gamma\) by any edge of \(G\)? For this problem, the authors provide instances for the existence of positive as well as negative answers. In this regard, the authors prove that \(\Gamma\) does not always exist if \(S\) is a spanning tree of \(G\); also they provide existential and algorithmic results for meaningful subfamilies of spanning trees and describe a linear-time testing and drawing algorithm when \(S\) is a triconnected spanning subgraph. Several open problems are also listed in the paper.