License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2020.53
URN: urn:nbn:de:0030-drops-129192
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12919/
Go to the corresponding LIPIcs Volume Portal

Förster, Henry ; Kaufmann, Michael

On Compact RAC Drawings

pdf-format:
LIPIcs-ESA-2020-53.pdf (1 MB)

Abstract

We present new bounds for the required area of Right Angle Crossing (RAC) drawings for complete graphs, i.e. drawings where any two crossing edges are perpendicular to each other. First, we improve upon results by Didimo et al. [Walter Didimo et al., 2011] and Di Giacomo et al. [Emilio Di Giacomo et al., 2011] by showing how to compute a RAC drawing with three bends per edge in cubic area. We also show that quadratic area can be achieved when allowing eight bends per edge in general or with three bends per edge for p-partite graphs. As a counterpart, we prove that in general quadratic area is not sufficient for RAC drawings with three bends per edge.

BibTeX - Entry

@InProceedings{frster_et_al:LIPIcs:2020:12919,
  author =	{Henry F{\"o}rster and Michael Kaufmann},
  title =	{{On Compact RAC Drawings}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{53:1--53:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Fabrizio Grandoni and Grzegorz Herman and Peter Sanders},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12919},
  URN =		{urn:nbn:de:0030-drops-129192},
  doi =		{10.4230/LIPIcs.ESA.2020.53},
  annote =	{Keywords: RAC drawings, visualization of dense graphs, compact drawings}
}

Keywords: RAC drawings, visualization of dense graphs, compact drawings
Collection: 28th Annual European Symposium on Algorithms (ESA 2020)
Issue Date: 2020
Date of publication: 26.08.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI