Simultaneous Visibility Representations of Plane st-graphs Using L-shapes

Let $⟨G_r,G_b⟩$ be a pair of plane $st$-graphs with the same vertex set $V$. A simultaneous visibility representation with L-shapes of $⟨G_r,G_b⟩$ is a pair of bar visibility representations $⟨{\mathrm{\Gamma }}_r,{\mathrm{\Gamma }}_b⟩$ such that, for every vertex $v\in V$, ${\mathrm{\Gamma }}_r(v)$ and ${\mathrm{\Gamma }}_b(v)$ are a horizontal and a vertical segment, which share an end-point. In other words, every vertex is drawn as an $L$-shape, every edge of $G_r$ is a vertical visibility segment, and every edge of $G_b$ is a horizontal visibility segment. Also, no two L-shapes intersect each other. An L-shape has four possible rotations, and we assume that each vertex is given a rotation for its L-shape as part of the input. Our main results are: (i) a characterization of those pairs of plane $st$-graphs admitting such a representation, (ii) a cubic time algorithm to recognize them, and (iii) a linear time drawing algorithm if the test is positive.