Veröffentlichung

Titel:

Simultaneous Drawing of Planar Graphs with Right-Angle Crossings and Few Bends

AutorInnen:

Michael A. Bekos
Thomas C. van Dijk
Philipp Kindermann
Alexander Wolff

Kategorie:

Artikel in Zeitschriften

erschienen in:

Journal of Graph Algorithms and Applications, Vol. 20, no. 1, 2016, pp. 133-158

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.

Download:

Journal Website

BibTeX-Eintrag:

@Article{bdkw-sdrac-jgaa16, Title = {Simultaneous Drawing of Planar Graphs with Right-Angle Crossings and Few Bends}, Author = {Michael A. Bekos and Thomas C. van Dijk and Philipp Kindermann and Alexander Wolff}, Journal = {Journal of Graph Algorithms and Applications}, Year = {2016}, Number = {1}, Pages = {133--158}, Volume = {20}, Abstract = {Given two planar graphs that are defined on the same set of vertices, a \emph{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.}, Booktitle = {Journal of Graph Algorithms and Applications}, Doi = {10.7155/jgaa.00388}, }