  An ortho-polygon visibility representation of an $n$-vertex embedded graph
$G$ (OPVR of $G$) is an embedding-preserving drawing of $G$ that maps every
vertex to a distinct orthogonal polygon and each edge to a vertical or
horizontal visibility between its end-vertices. The vertex complexity of an
OPVR of $G$ is the minimum $k$ such that every polygon has at most $k$ reflex
corners. We present polynomial time algorithms that test whether $G$ has an
OPVR and, if so, compute one of minimum vertex complexity. We argue that the
existence and the vertex complexity of an OPVR of $G$ are related to its number
of crossings per edge and to its connectivity. More precisely, we prove that if
$G$ has at most one crossing per edge (i.e., $G$ is a 1-plane graph), an OPVR
of $G$ always exists while this may not be the case if two crossings per edge
are allowed. Also, if $G$ is a 3-connected 1-plane graph, we can compute an
OPVR of $G$ whose vertex complexity is bounded by a constant in $O(n)$ time.
However, if $G$ is a 2-connected 1-plane graph, the vertex complexity of any
OPVR of $G$ may be $\Omega(n)$. In contrast, we describe a family of
2-connected 1-plane graphs for which an embedding that guarantees constant
vertex complexity can be computed in $O(n)$ time. Finally, we present the
results of an experimental study on the vertex complexity of ortho-polygon
visibility representations of 1-plane graphs.
