Dense circuit graphs and the planar Turán number of a cycle

The planar Turán number (Formula presented.) of a graph (Formula presented.) is the maximum number of edges in an (Formula presented.) -vertex planar graph without (Formula presented.) as a subgraph. Let (Formula presented.) denote the cycle of length (Formula presented.). The planar Turán number (Formula presented.) is known for (Formula presented.). We show that dense planar graphs with a certain connectivity property (known as circuit graphs) contain large near triangulations, and we use this result to obtain consequences for planar Turán numbers. In particular, we prove that there is a constant (Formula presented.) so that (Formula presented.) for all (Formula presented.) and (Formula presented.). When (Formula presented.) this bound is tight up to the constant (Formula presented.) and proves a conjecture of Cranston, Lidický, Liu, and Shantanam.

Duke Scholars

Author Ruilin Shi Mathematics