Obstacle Numbers of Planar Graphs.Gimbel, John and Ossona de Mendez, Patrice and Valtr, Pavel (2017) Obstacle Numbers of Planar Graphs. In: Graph Drawing and Network Visualization. GD 2017, September 2527 , pp. 6780(Official URL: https://doi.org/10.1007/9783319739151_6). Full text not available from this repository.
Official URL: https://doi.org/10.1007/9783319739151_6
Abstractiven finitely many connected polygonal obstacles O1,…,Ok in the plane and a set P of points in general position and not in any obstacle, the visibility graph of P with obstacles O1,…,Ok 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 PURE2DIR of intersection graphs of straight line segments in two directions) of order at least 3 is 1.
Actions (login required)
