The visibility graph of a set S ⊆ ℝ² is the graph whose vertices are the points of S, with two points x,y connected by an edge if and only if they see each other in S, that is, if the segment xy is contained in S. The edge density of this graph is known as the Beer index of S. Previously, it has been shown that a simply connected set S ⊆ ℝ² of unit Lebesgue measure with Beer index β > 0 contains a convex subset of measure Ω(β); in particular, for visibility graphs of simply connected sets, a positive edge density β > 0 implies the existence of a clique containing an Ω(β)-fraction of all vertices. The simple-connectivity assumption cannot be omitted, as there are non-simply-connected sets with Beer index 1 and no convex subset of positive measure. Nevertheless, in this paper, we extend the above result to non-simply-connected sets, by showing that a visibility graph with large edge density contains a triangle with large convex hull. More precisely, we show that a set S ⊆ ℝ² of unit Lebesgue measure with Beer index β > 0 contains three pairwise visible points whose convex hull has measure Ω(β⁹). If in addition S is an open domain with K holes, then S contains three pairwise visible points with convex hull of measure Ω(β/K) as well as a convex subset of measure Ω(β/K²).

We introduce a new complexity measure for cocomparability graphs of posets or in other words, intersection graphs of piecewise linear functions, the bend number. We prove that cocomparability graphs of bounded bend number are not too plentiful and give two hierarchies of classes of cocomparability graphs, depending on whether the piecewise linear functions are restricted to slopes of ±1 (diagonal case) or not (general case). These hierarchies give a gradation between permutation graphs and cocomparability graphs.

The dimension of a partial order $P$ is the minimum number of linear orders whose intersection is $P$. There are efficient algorithms to test if a partial order has dimension at most 2. In 1982 Yannakakis [SIAM J. Algebraic Discrete Methods, 3 (1982), pp. 351--358] showed that for $k\geq 3$ to test if a partial order has dimension $\leq k$ is NP-complete. The height of a partial order $P$ is the maximum size of a chain in $P$. Yannakakis also showed that for $k\geq 4$ to test if a partial order of height $2$ has dimension $\leq k$ is NP-complete. The complexity of deciding whether an order of height 2 has dimension 3 was left open. This question became one of the best known open problems in dimension theory for partial orders. We show that the problem is NP-complete. Technically, we show that the decision problem (3DH2) for dimension is equivalent to deciding for the existence of bipartite triangle containment representations (BTCon). This problem then allows a reduction from a class of planar satisfiability problems (P-3-CON-3-SAT(4)) which is known to be NP-hard.