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.
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].
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11590/298087
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 3
social impact