TY - JOUR
TI - Obstacles, slopes and tic-tac-toe
DO - https://doi.org/doi:10.7282/T3XD10QD
PY - 2011
AB - The minimum number of slopes used in a straight-line drawing of G is called the slope number of G. We show that every cubic graph can be drawn in the plane with straight line edges using only the four basic slopes {0, π/4, π/2,−π/4}. We also prove that four slopes have this property if and only if we can draw K4 with them. Given a graph G, an obstacle representation of G is a set of points in the plane representing the vertices of G, together with a set of obstacles (connected polygons)
such that two vertices of G are joined by an edge if and only if the corresponding points can be connected by a segment which avoids all obstacles. The obstacle number of G is the minimum number of obstacles in an obstacle representation of G. We show that there are graphs on n vertices with obstacle number (n/log n). We show that there is an m = 2n + o(n), such that, in the Maker-Breaker game played on Zd where Maker needs to put at least m of his marks consecutively in one
of n given winning directions, Breaker can force a draw using a pairing strategy. This improves the result of Kruczek and Sundberg who showed that such a pairing strategy exits if m ≥ 3n. A simple argument shows that m has to be at least 2n+1 if Breaker is only allowed to use a pairing strategy, thus the main term of our bound is optimal.
KW - Mathematics
KW - Combinatorial analysis
KW - Discrete geometry
KW - Mathematical models
LA - eng
ER -