Anzeige
Erschienen in:
2010 | OriginalPaper | Buchkapitel
Graphs with Large Obstacle Numbers
verfasst von : Padmini Mukkamala, János Pach, Deniz Sarıöz
Erschienen in: Graph Theoretic Concepts in Computer Science
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Motivated by questions in computer vision and sensor networks, Alpert et al. [3] introduced the following definitions. 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 an 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 was shown in [3] that there exist graphs of
n
vertices with obstacle number at least
$\Omega(\sqrt{\log n})$
. We use extremal graph theoretic tools to show that (1) there exist graphs of
n
vertices with obstacle number at least Ω(
n
/log
2
n
), and (2) the total number of graphs on
n
vertices with bounded obstacle number is at most
$2^{o(n^2)}$
. Better results are proved if we are allowed to use only
convex
obstacles or polygonal obstacles with a small number of sides.