Ortho-polygon visibility representations of 3-connected 1-plane graphs

An ortho-polygon visibility representation (OPVR) of an embedded graph G is an embedding-preserving drawing that maps each vertex of G to a distinct orthogonal polygon and each edge of G to a vertical or horizontal visibility between its end-vertices. An OPVR Gamma has vertex complexity kif every polygon of Gamma has at most k reflex corners. A 1-plane graph is an embedded graph such that each edge is crossed at most once. It is known that 3-connected 1-plane graphs admit an OPVR with vertex complexity at most 12, while vertex complexity at least 2 may be required in some cases. In this paper, we reduce this gap by showing that vertex complexity 5 is always sufficient, while vertex complexity 4 may be sometimes required. These results are based on the study of the combinatorial properties of the B-, T-, and W-configurations in 3-connected 1-plane graphs. An implication of the upper bound is the existence of a (O) over tilde (n(10/7))-time drawing algorithm that computes an OPVR of an n-vertex 3-connected 1-plane graph on an integer grid of size O(n) x O(n) and with vertex complexity at most 5. (C) 2021 Elsevier B.V. All rights reserved.

Automated summary

The paper explores the concept of ortho-polygon visibility representation (OPVR) in embedded graphs, introduces the notion of vertex complexity, and demonstrates that a vertex complexity of 5 is always sufficient in 3-connected 1-plane graphs, while sometimes a complexity of 4 may be required.