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 S are not crossed in Γ by any edge of G? We give positive and negative results for different kinds of connected 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 not in S; in this setting we discuss different trade-offs between the number of bends and the required drawing area.
Angelini, P., Binucci, C., DA LOZZO, G., Didimo, W., Grilli, L., Montecchiani, F., et al. (2015). Algorithms and Bounds for Drawing Non-planar Graphs with Crossing-free Subgraphs. COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 50, 34-48 [10.1016/j.comgeo.2015.07.002].
Algorithms and Bounds for Drawing Non-planar Graphs with Crossing-free Subgraphs
ANGELINI, PATRIZIO;DA LOZZO, GIORDANO;PATRIGNANI, Maurizio;
2015-01-01
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 Γ of G in the plane such that the edges of S are not crossed in Γ by any edge of G? We give positive and negative results for different kinds of connected 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 not in S; in this setting we discuss different trade-offs between the number of bends and the required drawing area.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
