How Long Can a Graph be Kept Planar?
V. Anuradha, Chinmay Jain, Jack Scott Snoeyink, Tibor Szabó · The Electronic Journal of Combinatorics · 2008
Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.
The Electronic Journal of Combinatorics · Electronic Journal of Combinatorics · article · 2008
Abstract
The graph (non-)planarity game is played on the complete graph $K_n$ between an Enforcer and an Avoider, each of whom take one edge per round. The game ends when the edges chosen by Avoider form a non-planar subgraph. We show that Avoider can play for $3n-26$ turns, improving the previous bound of $3n-28\sqrt n$.
Open the resolved locator · 10.37236/889
Metadata licence: OpenAlex metadata (CC0)