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 Γ? We give positive and negative results for different kinds of 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 ∖ S; in this setting different trade-offs between number of bends and drawing area are given. -
Angelini, P., Carla, B., DA LOZZO, G., Walter, D., Luca, G., Montecchiani, F., et al. (2013). Drawing Non-planar Graphs with Crossing-free Subgraphs. In Proc. of 21st International Symposium on Graph Drawing - GD '13 (pp.295-307). Berlin : SPRINGER-VERLAG [10.1007/978-3-319-03841-4_26].
Drawing Non-planar Graphs with Crossing-free Subgraphs
ANGELINI, PATRIZIO;DA LOZZO, GIORDANO;MONTECCHIANI , FABRIZIO;PATRIGNANI, Maurizio;
2013-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 Γ? We give positive and negative results for different kinds of 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 ∖ S; in this setting different trade-offs between number of bends and drawing area are given. -I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
