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.
|Titolo:||Algorithms and Bounds for Drawing Non-planar Graphs with Crossing-free Subgraphs|
|Data di pubblicazione:||2015|
|Citazione:||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.|
|Appare nelle tipologie:||1.1 Articolo in rivista|