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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
