A visibility drawing \(\varGamma \) of a planar graph G maps the vertices into non-overlapping horizontal segments (bars), and the edges into vertical segments (visibilities), each connecting the two bars corresponding to its two end-vertices. Visibilities intersect bars only at their extreme points. In a strong visibility drawing, there exists a visibility between two bars if and only if there exists an edge in G between the corresponding vertices. Conversely, in a weak visibility drawing, a visibility may not correspond to an edge of the graph. Every planar graph admits a weak visibility drawing [9].

The problem of extending visibility drawings to non-planar graphs has been first addressed by Dean et al. [3]. They introduce bar k-visibility drawings, which are visibility drawings where each bar can see through at most k distinct bars. In other words, each visibility segment can intersect at most k bars, while each bar can be intersected by arbitrary many visibility segments. The graphs that admit a bar 1-visibility drawing are called 1-visibile. Brandenburg and independently Evans et al. prove that 1-planar graphs, i.e., those graphs that can be drawn with at most one crossing per edge, are 1-visible [1, 5]. They focus on a weak model, where there is a visibility through at most k bars if there is an edge, while the converse may not be true. In terms of readability, a clear benefit of bar k-visibility drawings is that the crossings form right angles. Right-angle crossing (RAC) drawings and their advantages in terms of readability have been extensively studied in the graph drawing literature (see, e.g., [4]). However, in a bar k-visibility drawing crossings involve bars and visibilities, i.e., vertices and edges. These crossings are arguably less intuitive than crossings between edges.

Evans et al. introduce a new model of visibility drawings, called L-visibility drawings [6]. Their aim is to simultaneously represent two plane st-graphs \(G_r\) and \(G_b\) (whose union might be non-planar). Each vertex is represented by a horizontal bar and a vertical bar that share an extreme point, i.e. it is an L-shape in the set

figure a

. They assume a strong model, where two L-shapes are connected by a vertical (horizontal) visibility segment if and only if there exists an edge in \(G_r\) (\(G_b\)) between the corresponding vertices. Also, no two L-shapes cross one another, and visibilities intersect bars only at their extreme points. The only crossings are between vertical and horizontal visibilites, i.e., between edges of the graph. These crossings form right angles.

Fig. 1.
figure 1

(a) An IC-plane graph G. (b) An L-visibility drawing of G. (c) A RAC drawing of G.

Full size image

In this poster we present results on weak L-visibility drawings of non-planar graphs. We focus on IC-planar graphs, which are those graphs that admit a drawing where each edge is crossed at most once, and no two crossed edges share an end-vertex (see , e.g., Fig. 1(a)). Their chromatic number is at most five [7], and they have at most\(13n/4-6\) edges, which is a tight bound [10]. Recognizing IC-planar graphs is NP-hard [2].

Our main contribution is summarized by the following theorem. See Fig. 1(b) for an example of a L-visibility drawing computed by using Theorem 1.

FormalPara Theorem 1

Every n-vertex IC-plane graph G admits an L-visibility drawing in \(O(n^2)\) area, which can be computed in O(n) time.

Theorem 1 contributes to the rapidly growing literature devoted to the problem of drawing “nearly planar” graphs, where only some types of edge crossings are allowed. Brandenburg et al. recently described a cubic-time algorithm that computes straight-line RAC drawings of IC-planar graphs. These drawings may require exponential area, which is worst-case optimal [2]. They leave as an open problem to study techniques that compute IC-planar drawings in polynomial area and with good crossing resolution [2]. As a byproduct of Theorem 1, we obtain the following corollary (see Fig. 1(c)).

FormalPara Corollary 1

Every n-vertex IC-plane graph G admits a RAC drawing with at most two bends per edge in \(O(n^2)\) area, which can be computed in O(n) time.

For complete proofs of the presented results the reader can refer to [8].