2013/06/12 by Koch, Alexander, Krug, Marcus, Rutter, Ignaz
#Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1306.2978
An obstacle representation of a graph consists of a set of polygonal obstacles and a distinct point for each vertex such that two points see each other if and only if the corresponding vertices are adjacent. Obstacle representations are a recent generalization of classical polygon--vertex visibility graphs, for which the characterization and recognition problems are long-standing open questions. In this paper, we study plane outside-obstacle representations, where all obstacles lie in the unbounded face of the representation and no two visibility segments cross. We give a combinatorial characterization of the biconnected graphs that admit such a representation. Based on this characterization, we present a simple linear-time recognition algorithm for these graphs. As a side result, we show that the plane vertex--polygon visibility graphs are exactly the maximal outerplanar graphs and that every chordal outerplanar graph has an outside-obstacle representation.