文章基本信息

标题：A Universal Slope Set for 1-Bend Planar Drawings
本地全文：下载
作者：Patrizio Angelini ; Michael A. Bekos ; Giuseppe Liotta 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：77
页码：9:1-9:16
DOI：10.4230/LIPIcs.SoCG.2017.9
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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).
关键词：Slope number; 1-bend drawings; planar graphs; angular resolution