How long can a graph be kept planar?

MaRDI QIDQ1010669zbMATH OpenFDO

Authors V. Anuradha, Chinmay Jain, Tibor Szabó, Jack Snoeyink

Publication date 7 April 2009

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/129797, http://www.emis.de/journals/EJC/Volume_15/Abstracts/v15i1n14.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Positional games (pursuit and evasion, etc.) (91A24)

Review text

Summary: 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\).

Recommendations

• On winning fast in Avoider-Enforcer games
• Keeping avoider's graph almost acyclic
• On avoider-enforcer games
• Planarity, Colorability, and Minor Games
• Fast winning strategies in avoider-enforcer games

Cited in

(4)

• How unproportional must a graph be?
• The topology of competitively constructed graphs
• Fast winning strategies for the attacker in eternal domination
• Fast winning strategies in avoider-enforcer games

This page was built for publication: How long can a graph be kept planar?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1010669)