On the one-sided crossing minimization in a bipartite graph with large degrees (Q1770400)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the one-sided crossing minimization in a bipartite graph with large degrees |
scientific article |
Statements
On the one-sided crossing minimization in a bipartite graph with large degrees (English)
0 references
6 April 2005
0 references
Given a bipartite graph \(G=(V,W,E)\), a 2-layered drawing consists of placing nodes in the first node set \(V\) on a straight line \(L_1\) and placing nodes in the second node set \(W\) on a parallel line \(L_2\). For a given ordering of nodes in \(W\) on \(L_2\), the one-sided crossing minimization problem asks to find an ordering of nodes in \(V\) on \(L_1\) so that the number of arc crossings is minimized. A well-known lower bound \(LB\) on the minimum number of crossings is obtained by summing up \(\min c_{uv},c_{vu}\) over all node pairs \((u,v)\in V\), where \(c_{uv}\) denotes the number of crossings generated by arcs incident to \(u\) and \(v\) when \(u\) precedes \(v\) in an ordering. In this paper, we prove that there always exists a solution whose crossing number is at most \((1.2964+12/(\delta -4))LB\) if the minimum degree \(\delta\) of a node in \(V\) is at least 5.
0 references
Approximation algorithm
0 references
Bipartite graph
0 references
Edge crossing
0 references
Graph drawing
0 references
2-layered drawing
0 references
Randomized algorithm
0 references