期刊
JOURNAL OF COMBINATORIAL OPTIMIZATION
卷 46, 期 3, 页码 -出版社
SPRINGER
DOI: 10.1007/s10878-023-01084-9
关键词
Visibility graph; Rectangle visibility graph; Bar visibility graph
A rectangle visibility graph (RVG) represents rectangles in the plane and their unobstructed lines of sight. We study four measures of RVGs, namely area, perimeter, height, and width, and prove their independence. We also show that the empty graph may not have the largest measures for certain number of vertices.
A rectangle visibility graph (RVG) is represented by assigning to each vertex a rectangle in the plane with horizontal and vertical sides in such a way that edges in the graph correspond to unobstructed horizontal and vertical lines of sight between their corresponding rectangles. To discretize, we consider only rectangles whose corners have integer coordinates. For any given RVG, we seek a representation with smallest bounding box as measured by its area, perimeter, height, or width (height is assumed not to exceed width). We derive a number of results regarding these parameters. Using these results, we show that these four measures are distinct, in the sense that there exist graphs G(1) and G(2) with area(G(1)) < area(G(2)) but perim(G(2)) < perim(G(1)), and analogously for all other pairs of these parameters. We further show that there exists a graph G(3) with representations S-1 and S-2 such that area(G(3)) = area(S-1) < area(S-2) but perim(G(3)) = perim(S-2) < perim(S-1). In other words, G(3) requires distinct representations to minimize area and perimeter. Similarly, such graphs exist to demonstrate the independence of all other pairs of these parameters. Among graphs with n <= 6 vertices, the empty graph E-n requires largest area. But for graphs with n = 7 and n = 8 vertices, we show that the complete graphs K-7 and K-8 require larger area than E-7 and E-8, respectively. Using this, we show that for all n >= 8, the empty graph (E)n does not have largest area, perimeter, height, or width among all RVGs on n vertices.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据