Obstacle Numbers of Planar Graphs

Abstract

Given finitely many connected polygonal obstacles $O_1,\dots ,O_k$ in the plane and a set $P$ of points in general position and not in any obstacle, the {\em visibility graph} of $P$ with obstacles $O_1,\dots ,O_k$ is the (geometric) graph with vertex set $P$, where two vertices are adjacent if the straight line segment joining them intersects no obstacle. The obstacle number of a graph $G$ is the smallest integer $k$ such that $G$ is the visibility graph of a set of points with $k$ obstacles. If $G$ is planar, we define the planar obstacle number of $G$ by further requiring that the visibility graph has no crossing edges (hence that it is a planar geometric drawing of $G$). In this paper, we prove that the maximum planar obstacle number of a planar graph of order $n$ is $n-3$, the maximum being attained (in particular) by maximal bipartite planar graphs. This displays a significant difference with the standard obstacle number, as we prove that the obstacle number of every bipartite planar graph (and more generally in the class PURE-2-DIR of intersection graphs of straight line segments in two directions) of order at least $3$ is $1$.

Appears in the Proceedings of the 25th International Symposium on Graph Drawing and Network Visualization (GD 2017)