1-Bend Orthogonal Partial Edge Drawing

Abstract

Recently, a new layout style to avoid edge crossings in straight-line drawings of non-planar graphs received attention. In a Partial Edge Drawing (PED), the middle part of each segment representing an edge is dropped and the two remaining parts, called stubs, are not crossed. To help the user inferring the position of the two end-vertices of each edge, additional properties like symmetry and homogeneity are ensured in a PED. In this paper we explore this approach with respect to orthogonal drawings - a central concept in graph drawing. In particular, we focus on orthogonal drawings with one bend per edge, i.e., 1-bend drawings, and we define a new model called 1-bend Orthogonal Partial Edge Drawing, or simply 1-bend OPED. Similarly to the straight-line case, we study those graphs that admit 1-bend OPEDs when homogeneity and symmetry are required, where these two properties are defined so to support readability and avoid ambiguities. According to this new model, we show that every graph that admits a 1-bend drawing also admits a 1-bend OPED as well as 1-bend homogeneous orthogonal PED, i.e., a 1-bend HOPED. Furthermore, we prove that all graphs with maximum degree 3 admit a 1-bend symmetric and homogeneous orthogonal PED, i.e., a 1-bend SHOPED. Concerning graphs with maximum degree 4, we prove that the 2-circulant graphs that admit a 1-bend drawing also admit a 1-bend SHOPED, while there is a graph with maximum degree 4 that does not admit such a representation.