The Stub Resolution of 1-Planar Graphs
The Stub Resolution of 1-Planar Graphs
复制标题
1-平面图的存根解析
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
P. Valtr
中科院分区：
文献类型：
--
作者：
M. Kaufmann;Jan Kratochvíl;Fabian Lipp;Fabrizio Montecchiani;C. Raftopoulou;P. Valtr
绘图的分辨率在确定其质量标准时起着至关重要的作用。过去研究了网格分辨率、边长分辨率、角分辨率和交叉分辨率。本文研究了最近引入的一种非平面绘图判据——存根分辨率。一个交叉的边缘被分成几个部分，称为存根，为了便于阅读，存根不应该太短。因此，图纸的存根分辨率被定义为存根长度与整个边缘长度之间的最小比率，在图纸的所有边缘上。我们考虑了1-平面图，并探索了在每条边有0、1或2个弯的图中可以获得接近最优存根分辨率的场景，即任意接近（压裂b{1}{2}），以及进一步的分辨率标准，如角分辨率和交叉分辨率。特别是，我们的主要贡献如下：(i)每个具有独立交叉边的1-平面图都具有接近最优存根分辨率的直线绘制；（ii）每个1-平面图都有一个接近最优存根分辨率的1-弯曲图。
The resolution of a drawing plays a crucial role when defining criteria for its quality. In the past, grid resolution, edge-length resolution, angular resolution and crossing resolution have been investigated. In this paper, we investigate the stub resolution, a recently introduced criterion for nonplanar drawings. A crossed edge is divided into parts, called stubs, which should not be too short for the sake of readability. Thus, the stub resolution of a drawing is defined as the minimum ratio between the length of a stub and the length of the entire edge, over all the edges of the drawing. We consider 1-planar graphs and we explore scenarios in which near optimal stub resolution, i.e. arbitrarily close to (frac{1}{2}), can be obtained in drawings with zero, one, or two bends per edge, as well as further resolution criteria, such as angular and crossing resolution. In particular, our main contributions are as follows: (i) Every 1-planar graph with independent crossing edges has a straight-line drawing with near optimal stub resolution; (ii) Every 1-planar graph has a 1-bend drawing with near optimal stub resolution.