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.
Algorithms and bounds for drawing non-planar graphs with crossing-free subgraphs
BINUCCI, Carla;DIDIMO, WALTER;GRILLI, LUCA;MONTECCHIANI, FABRIZIO;
2015
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.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
