Geometric RAC Simultaneous Drawings of Graphs

Abstract

In this paper, we study the geometric RAC simultaneous drawing problem: Given two planar graphs that share a common vertex set, a geometric RAC simultaneous drawing is a straight-line drawing in which each graph is drawn planar, there are no edge overlaps, and, crossings between edges of the two graphs occur at right angles. We first prove that two planar graphs admitting a geometric simultaneous drawing may not admit a geometric RAC simultaneous drawing. We further show that a cycle and a matching always admit a geometric RAC simultaneous drawing. We also study a closely related problem according to which we are given a planar embedded graph $G$ and the main goal is to determine a geometric drawing of $G$ and its weak dual $G^*$ such that: (i) $G$ and $G^*$ are drawn planar, (ii) each vertex of the dual is drawn inside its corresponding face of $G$ and, (iii) the primal-dual edge crossings form right angles. We prove that it is always possible to construct such a drawing if the input graph is an outerplanar embedded graph