Originators: Sugiyama or Nagamochi
(presented by Matthew Yancey - REGS 2010)
Definitions: A horizontal drawing of a bipartite graph is a drawing of the graph in the plane such that the vertices of each partite set lie on a line and the two lines are parallel and distinct, with each edge drawn as a straight line. A radial drawing of a bipartite graph is a drawing of the graph in the plane such that the vertices of each part lie on a circle and the two circles are concentric and distinct, with edges contained inside the annulus defined by the circles.
The crossing number of a graph G, written cr(G), is the minimum, among drawings of the graph in the plane, of the total number of crossings of pairs of edges in the drawing. When G is bipartite, let crhor(G) be this minimum among the horizontal drawings of G, and let crrad(G) be the minimum only among radial drawings. (We consider only bipartite graphs.)
Background: Computing crhor(G) is NP-complete (Eades & Wormald [EW]; Garey & Johnson [GJ]), as is computing crrad(G) (Bachmaier [B]). This motivates the search for algorithms to find approximate solutions. In particular, one seeks a lower bound and an algorithm to produce a drawing where the number of crossings is within a constant factor of that lower bound.
Let X and Y be the two partite sets of G. Given a drawing, let σ be the order of Y along its line (or circle), and let π be the order of X. Fixing the order σ of Y along its line, for u,v∈X let cr(u,v,σ,G) be the number of crossings in any drawing formed by the edges incident to u and v when they appear in that order in π (in a radial drawing, cr(u,v,σ,G) is not affected by the order of u and v).
Let LB(G,σ) = ½ ∑ u≠v min{cr(u,v,σ,G), cr(v,u,σ,G)}, and let opt(G,σ) = minπ ∑π(u)<π(v) cr(u,v,σ,G). The definition of LB is motivated by the existence of algorithms proving that opt(G,σ) ≤ c LB(G,σ) for some constant c.
Question 1: What is supG, σ opt(G,σ) / LB(G,σ) ? Note here that σ is given, and we are not attempting to optimize over the choice of &sigma.
Comments: The best known algorithm finds a drawing with at most 1.4664 LB(G,σ) crossings (Nagamochi [N]). The same paper provides a graph and an order σ such that opt(G,σ) = 13/11 LB(G,σ). Thus the answer is bounded between 1.1818 and 1.4664. In the graph establishing the lower bound, Y consists of 16 vertices with degree 1, and |X|=3. The algorithm establishing the upper bound uses probabilistic techniques.
It may be possible to approach Question 1 using combinatorial structures. The values of cr(u,v,σ,G) yield an antisymmetric relation, and opt diverges from LB only when transitivity fails. Some algorithms create π as a linear extension of a poset: if one orders X by the order of median neighbors in σ, the number of crossings in the resulting drawing is at most 3⋅LB(G,σ). Both in the bounds and in the algorithms, poset-like structure seems relevant.
For radial drawings, an algorithm by Hong & Nagamochi [HN] produces a drawing within a constant factor of the optimal number of crossings (again given σ). The paper first produces a radial drawing with at most three times the optimal number of crossings that has an edge crossing no other edge. It uses that edge to cut the circles into lines and uses horizontal drawing techniques on the resulting graph.
Problem 2: Find a function similar to LB(G,σ) for radial graphs. This would require an analogue of cr(u,v,σ,G).
Comments: Problem 2 is rather open-ended. Due to the cyclical nature of radial drawings, analogues of cr(u,v,σ,G) to describe options in the ordering π should use at least three vertices. This would make transitivity for a poset-like structure describing π hard to find; it would also complicate proofs of performance ratios. A solution might, however, lead to an algorithm that does not involve a reduction to the horizontal problem.
References:
[B] C. Bachmaier, A Radial Adaptation of the Sugiyama Framework for Visualizing
Hierarchical Information, IEEE Transactions on Visualization and Computer
Graphics, Volume 13 , Issue 3 (2007), 583-594
[EW] Eades, Peter; Wormald, Nicholas C.; Edge crossings in drawings of
bipartite graphs. Algorithmica 11 (1994), no. 4, 379--403.
[GJ] Garey, M. R.; Johnson, D. S.; Crossing number is NP-complete. SIAM J.
Algebraic Discrete Methods 4 (1983), no. 3, 312--316.
[N] Hiroshi Nagamochi, An improved bound on the one-sided minimum crossing
number in two-layered drawings, Discrete Comput Geom. 33 (2005) 565-591
[HN] Seok-Hee Hong and Hiroshi Nagamochi, Approximation algorithms for
minimizing edge crossing in radial drawings, Algorithmica. (published online)
Jan 22, 2009