Logo der Fakultät Logo LG Theoretische Informatik
 

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: Sonstiges
erschienen in: Proceedings of the 23rd International Symposium on Graph Drawing (GD'14), pp. 515-516, Poster
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: Poster
BibTeX-Eintrag: @InProceedings{bdkw-sdrac-gd14poster, 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}, Booktitle = {Proceedings of the 23rd International Symposium on Graph Drawing (GD'14)}, Year = {2014}, Editor = {Christian A. Duncan and Antonios Symvonis}, Note = {Poster}, Pages = {515--516}, Publisher = {Springer}, Series = {Lecture Notes in Computer Science}, Volume = {8871}, 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.}, Doi = {10.1007/978-3-662-45803-7} }
Philipp Kindermann | 29.01.2016
FernUni-Logo FernUniversität in Hagen, LG Theoretische Informatik, 58084 Hagen