Layouts of cubic graphs

The graph-theoretic input to the lower bound is a layout bound for subcubic multigraphs, Frontier.LayoutBound 3 A. Compressing a subcubic multigraph to its cubic core reduces it to laying out simple cubic graphs (Frontier.Layouts.Compression).

CubicLayoutBound c says that for every ξ > 0, every sufficiently large simple cubic graph on h vertices has a layout, given as an injective vertex key, all of whose prefixes are crossed by at most (c + ξ) h + 2 edges. A cubic graph on h vertices has cycle rank h/2 + 1, which is why a cubic coefficient c becomes the layout coefficient 2c.

def Complexity.Frontier.CubicLayoutBound (c : ℝ) : Prop

The cubic layout bound with coefficient c: for every ξ > 0, every simple cubic graph on h vertices, for h large enough, has an injective vertex key all of whose prefixes {w | key w < t} are crossed by at most (c + ξ) h + 2 edges.

Equations

• One or more equations did not get rendered due to their size.