The convex-polygon realization conjecture for maximum rectilinear crossing numbers

Let GG be any graph. A rectilinear drawing represents the vertices of GG by points in the plane and its edges by straight-line segments. A convex-polygon drawing is one in which all vertices are vertex points of a convex polygon.

Convex-polygon realization conjecture. The maximum rectilinear crossing number of GG can be realized in a convex-polygon drawing.

If true, this would reduce the search for maximum rectilinear crossing numbers to drawings with all vertices in convex position. The paper presents this as a general conjecture useful for determining the maximum rectilinear crossing number.

Sources & referencesView supporting material

Primary source

Matthew Alpert, Elie Feder and Heiko Harborth, “The Maximum of the Maximum Rectilinear Crossing Numbers of d-regular Graphs of Order n”, arXiv:0812.1917 (2008).

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.