论文标题
图形的单位长度矩形图
Unit-length Rectangular Drawings of Graphs
论文作者
论文摘要
平面图$ g $的矩形图是$ g $的平面图，其中顶点映射到网格点，边缘映射到水平和垂直直线段，并将面部绘制为矩形。有时，后一种约束对外脸放松。在本文中，我们研究边缘具有单位长度的矩形图。我们显示了确定单位长度矩形图的存在问题的复杂性二分法，具体取决于是否还必须将外表面作为矩形绘制。具体而言，我们证明，当不需要外表面的绘制不需要矩形时，即使寻求的图纸必须尊重给定的平面嵌入，但如果需要在固定的固定和可变的嵌入设置中，则需要尊重给定的平面嵌入，而在固定的嵌入式设置中，则该问题是NP完整的。
A rectangular drawing of a planar graph $G$ is a planar drawing of $G$ in which vertices are mapped to grid points, edges are mapped to horizontal and vertical straight-line segments, and faces are drawn as rectangles. Sometimes this latter constraint is relaxed for the outer face. In this paper, we study rectangular drawings in which the edges have unit length. We show a complexity dichotomy for the problem of deciding the existence of a unit-length rectangular drawing, depending on whether the outer face must also be drawn as a rectangle or not. Specifically, we prove that the problem is NP-complete for biconnected graphs when the drawing of the outer face is not required to be a rectangle, even if the sought drawing must respect a given planar embedding, whereas it is polynomial-time solvable, both in the fixed and the variable embedding settings, if the outer face is required to be drawn as a rectangle.
