Search

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 Γ has vertex complexity k if every polygon of Γ 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 ˜ (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) × O (n) and with vertex complexity at most 5. [ABSTRACT FROM AUTHOR]

It is proved that every series-parallel digraph whose maximum vertex degree is Δ admits an upward planar drawing with at most one bend per edge such that each edge segment has one of Δ distinct slopes. The construction is worst-case optimal in terms of the number of slopes, and it gives rise to drawings with optimal angular resolution π Δ. A variant of the drawing algorithm is used to show that (non-directed) reduced series-parallel graphs and flat series-parallel graphs have a (non-upward) 1-bend planar drawing with ⌈ Δ 2 ⌉ distinct slopes if biconnected, and with ⌈ Δ 2 ⌉ + 1 distinct slopes if connected. [ABSTRACT FROM AUTHOR]