2010/12/29 by János Pach, Pach, János, Deniz Sarıöz +2
Computer Science · Engineering · Mathematics · #05C62 #05C85 #68R10 #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #G.2.2 #Smart Parking Systems Research #acm:05C62 #acm:05C85 #acm:68R10 #cs.CG #cs.DM #math.CO #msc:05C62 #msc:05C85 #msc:68R10
paper · pdf · doi:10.48550/arxiv.1012.5907
14 pages, 13 figures, ancillary to: Janos Pach and Deniz Sarioz, "On the structure of graphs with low obstacle number", Graphs and Combinatorics, Volume 27, Number 3, issue entitled "The Japan Conference on Computational Geometry and Graphs (JCCGG2009)", 465-473, DOI: 10.1007/s00373-011-1027-0, Springer, 2011. URL: http://www.springerlink.com/content/131r0n307h488825/
openalex publication_date 2010/12/29 · arxiv created 2011/04/24 · arxiv updated 2015/03/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An obstacle representation of a graph G is a set of points on the plane together with a set of polygonal obstacles that determine a visibility graph isomorphic to G. The obstacle number of G is the minimum number of obstacles over all obstacle representations of G. Alpert, Koch, and Laison gave a 12-vertex bipartite graph and proved that its obstacle number is two. We show that a 10-vertex induced subgraph of this graph has obstacle number two. Alpert et al. also constructed very large graphs with vertex set consisting of a clique and an independent set in order to show that obstacle number is an unbounded parameter. We specify a 70-vertex graph with vertex set consisting of a clique and an independent set, and prove that it has obstacle number greater than one. This is an ancillary document to our article in press. We conclude by showing that a 10-vertex graph with vertex set consisting of two cliques has obstacle number greater than one, improving on a result therein.