文章基本信息

标题：Strongly Monotone Drawings of Planar Graphs
本地全文：下载
作者：Stefan Felsner ; Alexander Igamberdiev ; Philipp Kindermann 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：51
页码：37:1-37:15
DOI：10.4230/LIPIcs.SoCG.2016.37
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：A straight-line drawing of a graph is a monotone drawing if for each pair of vertices there is a path which is monotonically increasing in some direction, and it is called a strongly monotone drawing if the direction of monotonicity is given by the direction of the line segment connecting the two vertices. We present algorithms to compute crossing-free strongly monotone drawings for some classes of planar graphs; namely, 3-connected planar graphs, outerplanar graphs, and 2-trees. The drawings of 3-connected planar graphs are based on primal-dual circle packings. Our drawings of outerplanar graphs depend on a new algorithm that constructs strongly monotone drawings of trees which are also convex. For irreducible trees, these drawings are strictly convex.
关键词：graph drawing; planar graphs; strongly monotone; strictly convex; primal-dual circle packing