Drawing graphs using a small number of obstacles

Abstract: An obstacle representation of a graph

G

is a set of points in the plane representing the vertices of

G

, together with a set of polygonal obstacles such that two vertices of

G

are connected by an edge in

G

if and only if the line segment between the corresponding points avoids all the obstacles. The obstacle number

m o b s (G)

of

G

is the minimum number of obstacles in an obstacle representation of

G

. We provide the first non-trivial general upper bound on the obstacle number of graphs by showing that every

n

-vertex graph

G

satisfies

m o b s (G) l e q n l c e i l l o g n c e i l - n + 1

. This refutes a conjecture of Mukkamala, Pach, and P'alv"olgyi. For

n

-vertex graphs with bounded chromatic number, we improve this bound to

O (n)

. Both bounds apply even when the obstacles are required to be convex. We also prove a lower bound

2^{O m e g a (h n)}

on the number of

n

-vertex graphs with obstacle number at most

h

for

h < n

and a lower bound

O m e g a (n^{4 / 3} M^{2 / 3})

for the complexity of a collection of

M g e q O m e g a (n l o g^{3 / 2} n)

faces in an arrangement of line segments with

n

endpoints. The latter bound is tight up to a multiplicative constant.

Cites Work

Cited In (9)

This page was built for publication: Drawing graphs using a small number of obstacles