Heuristics for the Maximum 2-Layer RAC Subgraph Problem. Di Giacomo, E.; Didimo, W.; Grilli, L.; Liotta, G.; and Romeo, S. A. COMPUTER JOURNAL, 58:1085–1098, 2014.
Heuristics for the Maximum 2-Layer RAC Subgraph Problem [link]Paper  doi  abstract   bibtex   
A 2-layer drawing of a bipartite graph G is a drawing such that the vertices of each partition set are drawn as points of a distinct horizontal line (called a layer) and the edges are drawn as straight-line segments. We study 2-layer drawings where edges can cross only at right angles; these drawings are called 2-layer right angle crossing drawings (2-layer RAC drawings for short). We focus on the following problem, which we call the maximum 2-layer RAC subgraph (M2LRacS) problem. Given a bipartite graph G, compute a subgraph H of G such that: (i) H admits a 2-layer RAC drawing and (ii) H has the maximum number of edges among the subgraphs of G that satisfy (i). We study this problem both in the no-fixed-layer setting, where no restriction is given on the vertex ordering on each layer, and in the 1-fixed-layer setting, where the ordering of the vertices of one of the two layers is given as part of the input and cannot be changed. The M2LRacS problem is known to be NP-hard in the no-fixed-layer setting, but no algorithm has been proposed so far to solve it. We prove that the M2LRacS problem remains -hard even in the 1-fixed-layer setting, and provide different heuristics to solve it in the two settings; one of these heuristics is a 3-approximation algorithm for the no-fixed-layer setting. Also, we present the results of an experimental study that compares our heuristics and shows the effectiveness of the 3-approximation algorithm in practice.
@article{
	11391_1219305,
	author = {Di Giacomo, E. and Didimo, W. and Grilli, L. and Liotta, G. and Romeo, S. A.},
	title = {Heuristics for the Maximum 2-Layer RAC Subgraph Problem},
	year = {2014},
	journal = {COMPUTER JOURNAL},
	volume = {58},
	abstract = {A 2-layer drawing of a bipartite graph G is a drawing such that the vertices of each partition set are drawn as points of a distinct horizontal line (called a layer) and the edges are drawn as straight-line segments. We study 2-layer drawings where edges can cross only at right angles; these drawings are called 2-layer right angle crossing drawings (2-layer RAC drawings for short). We focus on the following problem, which we call the maximum 2-layer RAC subgraph (M2LRacS) problem. Given a bipartite graph G, compute a subgraph H of G such that: (i) H admits a 2-layer RAC drawing and (ii) H has the maximum number of edges among the subgraphs of G that satisfy (i). We study this problem both in the no-fixed-layer setting, where no restriction is given on the vertex ordering on each layer, and in the 1-fixed-layer setting, where the ordering of the vertices of one of the two layers is given as part of the input and cannot be changed. The M2LRacS problem is known to be NP-hard in the no-fixed-layer setting, but no algorithm has been proposed so far to solve it. We prove that the M2LRacS problem remains -hard even in the 1-fixed-layer setting, and provide different heuristics to solve it in the two settings; one of these heuristics is a 3-approximation algorithm for the no-fixed-layer setting. Also, we present the results of an experimental study that compares our heuristics and shows the effectiveness of the 3-approximation algorithm in practice.},
	keywords = {graph drawing, right angle crossings, bipartite graphs, heuristics, experimental study},
	url = {http://comjnl.oxfordjournals.org/content/58/5/1085},
	doi = {10.1093/comjnl/bxu017},	
	pages = {1085--1098}
}
Downloads: 0