Computing Cartograms with Optimal Complexity
Computing Cartograms with Optimal Complexity
复制标题
以最佳复杂度计算制图
DOI：
--
复制
发表时间：
2011
影响因子：
0.8
通讯作者：
T. Ueckerdt
中科院分区：
文献类型：
--
作者：
M. J. Alam;T. Biedl;S. Felsner;M. Kaufmann;S. Kobourov;T. Ueckerdt
在平面图的直线对偶中，顶点由简单的直线多边形表示，而边由相应多边形之间的侧接触表示。如果每个区域的面积等于预先指定的权重，则直线对偶称为制图。地图的复杂性取决于任何多边形所需的最大角（或边）数量。在一系列论文中，最大平面图的此类表示的多边形复杂度已从最初的 40 减少到 34，然后减少到 12，最近减少到目前最著名的 10。这里我们描述了一种 8 边多边形的构造，就多边形复杂性而言，这是最佳的，因为有时需要 8 边多边形。具体来说，我们展示了如何计算组合结构以及如何在线性时间内将其细化为区域通用矩形布局。精确的地图可以通过数值迭代从区域通用布局中计算出来，或者可以通过爬山启发法来近似。我们还描述了哈密顿最大平面图的制图图的替代结构，它允许我们直接在线性时间内计算制图图。此外，我们通过构造一个非平凡的下界示例，证明即使对于哈密顿图，8 边直线多边形也是必要的。如果哈密顿路径具有单腿的额外属性（如外平面图中那样），则制图的复杂度可以减少到 6。因此，我们拥有哈密顿最大平面图和最大外平面图的最佳表示（就多边形复杂度和运行时间而言）。最后，我们解决了为 4 连通图（哈密顿图）构建小复杂度图表的问题。我们首先反驳了两组作者提出的猜想，即任何 4 连通最大平面图都具有单腿哈密顿循环，从而使在该图类的地图中实现多边形复杂度 6 的尝试无效。我们还证明，确定给定的 4 连通平面图是否包含相对于给定权重函数的制图是 NP 困难的。
In a rectilinear dual of a planar graph vertices are represented by simple rectilinear polygons, while edges are represented by side-contact between the corresponding polygons. A rectilinear dual is called a cartogram if the area of each region is equal to a pre-specified weight. The complexity of a cartogram is determined by the maximum number of corners (or sides) required for any polygon. In a series of papers the polygonal complexity of such representations for maximal planar graphs has been reduced from the initial 40 to 34, then to 12 and very recently to the currently best known 10. Here we describe a construction with 8-sided polygons, which is optimal in terms of polygonal complexity as 8-sided polygons are sometimes necessary. Specifically, we show how to compute the combinatorial structure and how to refine it into an area-universal rectangular layout in linear time. The exact cartogram can be computed from the area-universal layout with numerical iteration, or can be approximated with a hill-climbing heuristic. We also describe an alternative construction of cartograms for Hamiltonian maximal planar graphs, which allows us to directly compute the cartograms in linear time. Moreover, we prove that even for Hamiltonian graphs 8-sided rectilinear polygons are necessary, by constructing a non-trivial lower bound example. The complexity of the cartograms can be reduced to 6 if the Hamiltonian path has the extra property that it is one-legged, as in outer-planar graphs. Thus, we have optimal representations (in terms of both polygonal complexity and running time) for Hamiltonian maximal planar and maximal outer-planar graphs. Finally we address the problem of constructing small-complexity cartograms for 4-connected graphs (which are Hamiltonian). We first disprove a conjecture, posed by two set of authors, that any 4-connected maximal planar graph has a one-legged Hamiltonian cycle, thereby invalidating an attempt to achieve a polygonal complexity 6 in cartograms for this graph class. We also prove that it is NP-hard to decide whether a given 4-connected plane graph admits a cartogram with respect to a given weight function.