论文标题
部分可观测时空混沌系统的无模型预测
Parameterized Approaches to Orthogonal Compaction
论文作者
论文摘要
正交图纸用于UML图，VLSI布局，电缆计划和地铁图等应用中。我们专注于绘制平面图，并假设我们给出了描述所需形状的\ emph {正交表示}，但没有描述图形的确切坐标。我们的目的是计算网格上的正交图，该绘图在遵循给定正交表示的所有网格图中具有最小的面积。 这个问题称为正交压实（OC），即使是循环的正交表示，也被称为NP- hard [Evans等，2022]。我们研究了OC相对于多个参数的复杂性。除其他外，我们还表明，相对于这些参数中最自然的oc是固定参数，即正交表示的\ emph {kitty Corners}的数量：正交表示中的一对小猫角的存在使OC问题很难。从非正式的角度来看，一对小猫角是彼此相处的一对反射角。因此，小猫角的数量是一对小猫角角的角落数量。
Orthogonal graph drawings are used in applications such as UML diagrams, VLSI layout, cable plans, and metro maps. We focus on drawing planar graphs and assume that we are given an \emph{orthogonal representation} that describes the desired shape, but not the exact coordinates of a drawing. Our aim is to compute an orthogonal drawing on the grid that has minimum area among all grid drawings that adhere to the given orthogonal representation. This problem is called orthogonal compaction (OC) and is known to be NP-hard, even for orthogonal representations of cycles [Evans et al., 2022]. We investigate the complexity of OC with respect to several parameters. Among others, we show that OC is fixed-parameter tractable with respect to the most natural of these parameters, namely, the number of \emph{kitty corners} of the orthogonal representation: the presence of pairs of kitty corners in an orthogonal representation makes the OC problem hard. Informally speaking, a pair of kitty corners is a pair of reflex corners of a face that point at each other. Accordingly, the number of kitty corners is the number of corners that are involved in some pair of kitty corners.
