A hypergraph consists of a set of vertices and a set of subsets of vertices, called hyperedges. In the metro map metaphor, each hyperedge is represented by a path (the metro line) and the union of all these paths is the support graph (metro network) of the hypergraph. Formally speaking, a path-based support is a graph together with a set of paths. We consider the problem of constructing drawings of path-based supports that (i) minimize the sum of the number of bends on all paths, (ii) minimize the maximum number of bends on any path, or (iii) maximize the number of 0-bend paths, then the number of 1-bend paths, etc. We concentrate on straight-line drawings of path-based tree and cactus supports as well as orthogonal drawings of path-based plane supports with maximum degree 4.
翻译：超图由一组顶点和一组顶点的子集（称为超边）构成。在地铁图的隐喻中，每个超边由一条路径（地铁线路）表示，所有路径的并集构成超图的支持图（地铁网络）。形式化而言，基于路径的支持是一个图及其上的一组路径。我们研究基于路径的支持图的绘制问题，目标包括：（i）最小化所有路径的弯折总数，（ii）最小化任意路径的最大弯折数，或（iii）最大化0弯折路径的数量，其次最大化1弯折路径的数量，依此类推。我们重点关注基于路径的树和仙人掌图支撑的直线绘制，以及最大度为4的基于路径的平面图支撑的正交绘制。
相关内容
微信扫码咨询专知VIP会员