Loading...
research article
Lower bounds on the obstacle number of graphs
Given a graph G, an obstacle representation of G is a set of points in the plane representing the vertices of G, together with a set of connected obstacles such that two vertices of G are joined by an edge if and only if the corresponding points can be connected by a segment which avoids all obstacles. The obstacle number of G is the minimum number of obstacles in an obstacle representation of G. It is shown that there are graphs on n vertices with obstacle number at least Omega(n/logn).
Type
research article
Web of Science ID
WOS:000305145100007
Authors
Publication date
2012
Published in
Volume
19
Start page
P32
Peer reviewed
REVIEWED
EPFL units
Available on Infoscience
July 13, 2012
Use this identifier to reference this record