کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6854854 1437597 2018 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Heuristics for the min-max arc crossing problem in graphs
ترجمه فارسی عنوان
اکتشافات برای مشکل انتقال مینیمم قوس در نمودارها
کلمات کلیدی
نمودار کارشناس طراحی سیستم، متهوریستی، کاهش عبور، حرامزاده حرامزاده،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر هوش مصنوعی
چکیده انگلیسی
In this paper, we study the visualization of complex structures in the context of automatic graph drawing. Constructing geometric representations of combinatorial structures, such as networks or graphs, is a difficult task that requires an expert system. The automatic generation of drawings of graphs finds many applications from software engineering to social media. The objective of graph drawing expert systems is to generate layouts that are easy to read and understand. This main objective is achieved by solving several optimization problems. In this paper we focus on the most important one: reducing the number of arc crossings in the graph. This hard optimization problem has been studied extensively in the last decade, proposing many exact and heuristic methods to minimize the total number of arc crossings. However, despite its practical significance, the min-max variant in which the maximum number of crossings over all edges is minimized, has received very little attention. We propose new heuristic methods based on the strategic oscillation methodology to solve this NP-hard optimization problem. Our experimentation shows that the new method compares favorably with the existing ones, implemented in current graph drawing expert systems. Therefore, a direct application of our findings will improve these functionality (i.e., crossing reduction) of drawing systems.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Expert Systems with Applications - Volume 109, 1 November 2018, Pages 100-113
نویسندگان
, , , ,