The convex-polygon realization conjecture for maximum rectilinear crossing numbers
The convex-polygon realization conjecture for maximum rectilinear crossing numbers
Let be any graph. A rectilinear drawing represents the vertices of 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 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
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.