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.SoCG.2017.9
URN: urn:nbn:de:0030-drops-71917
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7191/
Go to the corresponding LIPIcs Volume Portal

Angelini, Patrizio ; Bekos, Michael A. ; Liotta, Giuseppe ; Montecchiani, Fabrizio

A Universal Slope Set for 1-Bend Planar Drawings

pdf-format:
LIPIcs-SoCG-2017-9.pdf (0.9 MB)

Abstract

We describe a set of Delta-1 slopes that are universal for 1-bend planar drawings of planar graphs of maximum degree Delta>=4; this establishes a new upper bound of Delta-1 on the 1-bend planar slope number. By universal we mean that every planar graph of degree Delta has a planar drawing with at most one bend per edge and such that the slopes of the segments forming the edges belong to the given set of slopes. This improves over previous results in two ways: Firstly, the best previously known upper bound for the 1-bend planar slope number was 3/2(Delta-1) (the known lower bound being 3/4(Delta-1)); secondly, all the known algorithms to construct 1-bend planar drawings with O(Delta) slopes use a different set of slopes for each graph and can have bad angular resolution, while our algorithm uses a universal set of slopes, which also guarantees that the minimum angle between any two edges incident to a vertex is pi/(Delta-1).

BibTeX - Entry

@InProceedings{angelini_et_al:LIPIcs:2017:7191,
  author =	{Patrizio Angelini and Michael A. Bekos and Giuseppe Liotta and Fabrizio Montecchiani},
  title =	{{A Universal Slope Set for 1-Bend Planar Drawings}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{9:1--9:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Boris Aronov and Matthew J. Katz},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7191},
  URN =		{urn:nbn:de:0030-drops-71917},
  doi =		{10.4230/LIPIcs.SoCG.2017.9},
  annote =	{Keywords: Slope number, 1-bend drawings, planar graphs, angular resolution}
}

Keywords: Slope number, 1-bend drawings, planar graphs, angular resolution
Collection: 33rd International Symposium on Computational Geometry (SoCG 2017)
Issue Date: 2017
Date of publication: 20.06.2017

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