2011/03/14 by Padmini Mukkamala, János Pach, Mukkamala, Padmini +3
Computer Science · Mathematics · #05C62 #05C75 #68R10 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #math.CO #msc:05C62 #msc:05C75 #msc:68R10
paper · pdf · doi:10.48550/arxiv.1103.2724
arxiv created 2011/03/14 · openalex publication_date 2011/03/14 · arxiv updated 2011/03/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a graph G, an \em 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 \em 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 Ω(n/log n).