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.

Abstract

iven 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.

Item Type:	Conference Paper
Classifications:	G Algorithms and Complexity > G.560 Geometry P Styles > P.540 Planar P Styles > P.900 Visibility
URI:	http://gdea.informatik.uni-koeln.de/id/eprint/1597

Actions (login required)

View Item