Ortho-polygon Visibility Representations of Embedded Graphs.

An ortho-polygon visibility representation of an <italic>n</italic>-vertex embedded graph <italic>G</italic> (OPVR of <italic>G</italic>) is an embedding-preserving drawing of <italic>G</italic> 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 <italic>G</italic> is the minimum <italic>k</italic> such that every polygon has at most <italic>k</italic> reflex corners. We present polynomial time algorithms that test whether <italic>G</italic> 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 <italic>G</italic> are related to its number of crossings per edge and to its connectivity. More precisely, we prove that if <italic>G</italic> has at most one crossing per edge (i.e., <italic>G</italic> is a 1-plane graph), an OPVR of <italic>G</italic> always exists while this may not be the case if two crossings per edge are allowed. Also, if <italic>G</italic> is a 3-connected 1-plane graph, we can compute an OPVR of <italic>G</italic> whose vertex complexity is bounded by a constant in <italic>O</italic>(<italic>n</italic>) time. However, if <italic>G</italic> is a 2-connected 1-plane graph, the vertex complexity of any OPVR of <italic>G</italic> may be Ω(n)<inline-graphic></inline-graphic>. 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 <italic>O</italic>(<italic>n</italic>) time. Finally, we present the results of an experimental study on the vertex complexity of ortho-polygon visibility representations of 1-plane graphs. [ABSTRACT FROM AUTHOR]