Firefighter Problem Simulator

Graph type

Nodes: 10

Click any node to start the fire there

Normal On fire Protected Burned Origin

Total nodes

—

Saved

—

Burned

—

Surviving rate

—

Round

—

Select a graph type, adjust size, then click a node to ignite.

Halin Graph — Optimal Strategy

A Halin graph is a rooted plane tree with all leaves connected by an outer cycle. This hierarchical + cyclic structure enables efficient fire containment.

Case 1 — Fire at a leaf

Protect the leaf's 2 cycle-neighbours and its tree-parent (3 firefighters, round 1). Fire is confined to 1 node — all n−1 remaining nodes are saved.

Case 2 — Fire at internal node

Protect the node's parent and 2 children. This partitions the graph into disjoint subtrees of size ≤ 2n/3. Fire cannot cross protected boundaries.

Budget: 3 firefighters in round 1, 2 per round thereafter.

Proven Bounds

Graph class	Worst-case	Asymptotic (n→∞)	Budget
General planar	ρ ≥ 2/21 ≈ 0.095	—	3+2/round
Halin graphs novel	ρ ≥ 1/6 ≈ 0.167	ρ ≥ 2/3 ≈ 0.667	3+2/round
Outerplanar graphs	ρ ≥ 1/3 ≈ 0.333	—	1+1/round

The Halin graph bound (1/6 worst-case, 2/3 asymptotic) is an original contribution of this project, improving upon the general planar bound of 2/21.

Halin Graph — Optimal Strategy

Outerplanar Graph — Separator Strategy

Proven Bounds