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 25-27 , pp. 67-80(Official URL: https://doi.org/10.1007/978-3-319-73915-1_6). Full text not available from this repository.
Official URL: https://doi.org/10.1007/978-3-319-73915-1_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 PURE-2-DIR of intersection graphs of straight line segments in two directions) of order at least 3 is 1.
Actions (login required)
|