Drawing Non-Planar Graphs with Crossing-Free Subgraphs

Angelini, Patrizio and Binucci, Carla and Da Lozzo, Giordano and Didimo, Walter and Grilli, Luca and Montecchiani, Fabrizio and Patrignani, Maurizio and Tollis, Ioannis G. (2013) Drawing Non-Planar Graphs with Crossing-Free Subgraphs. In: 21st International Symposium, GD 2013, September 23-25, 2013 , pp. 292-303(Official URL: http://dx.doi.org/10.1007/978-3-319-03841-4_26).

Full text not available from this repository.


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.

Item Type: Conference Paper
Classifications: G Algorithms and Complexity > G.999 Others
P Styles > P.540 Planar
P Styles > P.720 Straight-line
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1383

Actions (login required)

View Item View Item