Special Issue on Selected Papers from the Ninth International Workshop on Algorithms and Computation (WALCOM 2015)
Simultaneous Drawing of Planar Graphs with Right-Angle Crossings and Few Bends
Michael A. Bekos, Thomas C. van Dijk, Philipp Kindermann, and Alexander Wolff
Vol. 20, no. 1, pp. 133-158, 2016. Regular paper.
Abstract Given two planar graphs that are defined on the same set of vertices, a RAC simultaneous drawing is a drawing of the two graphs where each graph is drawn planar, no two edges overlap, and edges of one graph can cross edges of the other graph only at right angles. In the geometric version of the problem, vertices are drawn as points and edges as straight-line segments. It is known, however, that even pairs of very simple classes of planar graphs (such as wheels and matchings) do not always admit a geometric RAC simultaneous drawing. In order to enlarge the class of graphs that admit RAC simultaneous drawings, we allow edges to have bends. We prove that any pair of planar graphs admits a RAC simultaneous drawing with at most six bends per edge. For more restricted classes of planar graphs (e.g., matchings, paths, cycles, outerplanar graphs, and subhamiltonian graphs), we significantly reduce the required number of bends per edge. All our drawings use quadratic area.
Submitted: March 2015.
Reviewed: June 2015.
Revised: July 2015.
Accepted: August 2015.
Final: January 2016.
Published: February 2016.
Communicated by M. Sohel Rahman and Etsuj Tomita
article (PDF)