Some results on visibility graphs (Q1201816)

A visibility graph is a graph whose vertices are pairwise disjoint horizontal straight line segments such that two vertices are adjacent if and only if there is a vertical straight line intersecting only the two vertices under consideration. If the segments are allowed not to include the ends, visibility graphs have been characterized completely by R. Tamassia and I. G. Tollis: They are the planar graphs having an embedding such that all cutvertices are on the unbounded face. When the line segments must include the two ends, the situation is different as demonstrated in this paper: There are 3-connected planar graphs that are no visibility graphs, and the problem of recognizing such graphs is NP- complete.