2-degeneracy conjecture for strictly convex vertex and edge-midpoint drawings
2-degeneracy conjecture for strictly convex vertex and edge-midpoint drawings
A point set is strictly convex if every point is a vertex of its convex hull. For a graph , let be the class of graphs admitting a straight-line drawing in the plane in which the vertices form a strictly convex point set and the midpoints of the edges also form a strictly convex point set.
2-degeneracy conjecture. If , then is -degenerate; that is, every non-empty induced subgraph of has a vertex of degree at most .
The authors do not know any 3-regular graph in . The conjecture would imply strong structural and sparsity restrictions on graphs admitting these drawings, but the supplied text gives no resolution.
Sources & referencesView supporting material
Primary source
Ignacio García-Marco and Kolja Knauer, “Drawing graphs with vertices and edges in convex position”, arXiv:1509.01981 (2016).
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.