New Models and Methods for the Effective Orthogonal Layout of Graphs

图的有效正交布局的新模型和方法

• 批准号: 249458560
• 负责人: Professor Dr. Michael Kaufmann, Ph.D.
• 金额: --
• 依托单位: Fachbereich IV: Informatik
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2014
• 资助国家: 德国
• 起止时间: 2013-12-31 至 2022-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/249458560?language=en
• 关键词: New; Models; Methods; Effective; Orthogonal

Orthogonal graph drawing is an intensively studied and well-established model for drawing graphs, which traces back to VLSI layouts and floor-planning applications. Due to its high importance in practical applications, several efficient algorithms providing good aesthetics and good readability have been proposed over the years. However, due to the inherent limitations but also because of the simplicity of the model, there exist also some drawbacks that seem to be unavoidable. In the first phase of this project, we identified these drawbacks and suggested two main alternative models. The first model is the smooth orthogonal graph drawing model (Smog, for short), which combines the rigidity and clarity of orthogonal layouts with the artistic style and aesthetic appeal of the so-called Lombardi drawings.The second model is the slanted orthogonal drawing model (Slog, for short), which allows diagonal segments, while keeping the original orthogonal ports, in particular to simplify the recognizability of the crossings. In the first phase of the project, the research mainly focused on introducing methodological foundations. In the second phase, we plan to further continue our theoretical study and also to apply the knowledge we gained in the first phase of the project to diverse application areas aiming in integrating domain-specific requirements in our models.

正交图形是一个经过深入研究且建立了良好的图形模型，可追溯到VLSI布局和地板平面应用。由于其在实际应用中的重要性很高，多年来，已经提出了几种提供良好美学和良好可读性的有效算法。但是，由于固有的局限性，但由于模型的简单性，也存在一些似乎不可避免的缺点。在该项目的第一阶段，我们确定了这些缺点，并提出了两个主要的替代模型。第一个模型是光滑的正交图形模型（Smog，简称烟雾），它结合了正交布局的刚性和清晰度与艺术风格和所谓的Lombardi图纸的美感吸引力。 （简而言之），它允许对角线段，同时保持原始正交端口，特别是为了简化交叉口的可识别率。在项目的第一阶段，该研究主要集中于引入方法论基础。在第二阶段，我们计划进一步继续我们的理论研究，并将我们在项目第一阶段获得的知识应用于旨在在模型中集成域特异性需求的各种应用领域。