The linear edge bound conjecture for graphs with at most two bends
The linear edge bound conjecture for graphs with at most two bends
Let 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 on vertices, membership in means has such a drawing.
Linear edge bound conjecture. A graph on vertices belonging to the class can have at most edges.
The paper proves the weaker bound for graphs in ; the conjectured linear bound would further narrow the gap between the classes and .
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.