The linear edge bound conjecture for graphs with at most two bends

Let R2R_2 be the class of graphs that can be drawn in the plane with vertices as points and edges as polygonal arcs having at most two bends, such that any two edge-arcs cross at right angles and not at a bend. For a graph GG on nn vertices, membership in R2R_2 means GG has such a drawing.

Linear edge bound conjecture. A graph GG on nn vertices belonging to the class R2R_2 can have at most O(n)O(n) edges.

The paper proves the weaker bound O(nlog2n)O(n\log^2 n) for graphs in R2R_2; the conjectured linear bound would further narrow the gap between the classes R2R_2 and R3R_3.

Sources & referencesView supporting material

Primary source

Radoslav Fulek, Balázs Keszegh and Filip Morić, “Drawing Graphs with Orthogonal Crossings”, arXiv:1001.3117 (2010).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.