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 GG, let Gss\mathcal{G}_s^s 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 GGssG\in\mathcal{G}_s^s, then GG is 22-degenerate; that is, every non-empty induced subgraph of GG has a vertex of degree at most 22.

The authors do not know any 3-regular graph in Gss\mathcal{G}_s^s. 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

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.