Lower bounds on the obstacle number of graphs (Q426912)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Lower bounds on the obstacle number of graphs |
scientific article |
Statements
Lower bounds on the obstacle number of graphs (English)
0 references
12 June 2012
0 references
Summary: 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}/{\log n})\).
0 references
obstacle number
0 references
visibility graph
0 references
graph representation
0 references