This paper studies 2-layer RAC drawings of bipartite graphs. The contribution is as follows: (i) We prove that the problem of computing the maximum 2-layer RAC subgraph is NP-hard even when the vertex ordering on one layer is fixed; this extends a previous NP-hardness result that allows the vertices to be permuted on each layer. (ii) We describe a 3-approximation algorithm for the maximum 2-layer RAC subgraph problem when the vertex ordering on each layer is not fixed, and a heuristic for the case that the vertex ordering on one of the layers is fixed. (iii) We present an experimental study that evaluates the effectiveness of the proposed approaches.

Heuristics for the Maximum 2-layer RAC Subgraph Problem

DI GIACOMO, Emilio;DIDIMO, WALTER;GRILLI, LUCA;LIOTTA, Giuseppe;ROMEO, SALVATORE AGOSTINO
2012

Abstract

This paper studies 2-layer RAC drawings of bipartite graphs. The contribution is as follows: (i) We prove that the problem of computing the maximum 2-layer RAC subgraph is NP-hard even when the vertex ordering on one layer is fixed; this extends a previous NP-hardness result that allows the vertices to be permuted on each layer. (ii) We describe a 3-approximation algorithm for the maximum 2-layer RAC subgraph problem when the vertex ordering on each layer is not fixed, and a heuristic for the case that the vertex ordering on one of the layers is fixed. (iii) We present an experimental study that evaluates the effectiveness of the proposed approaches.
2012
9783642280757
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/11391/776898
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? ND
social impact