| dbo:abstract
|
- Layered graph drawing or hierarchical graph drawing is a type of graph drawing in which the vertices of a directed graph are drawn in horizontal rows or layers with the edges generally directed downwards. It is also known as Sugiyama-style graph drawing after Kozo Sugiyama, who first developed this drawing style. The ideal form for a layered drawing would be an upward planar drawing, in which all edges are oriented in a consistent direction and no pairs of edges cross. However, graphs often contain cycles, minimizing the number of inconsistently-oriented edges is NP-hard, and minimizing the number of crossings is also NP-hard, so layered graph drawing systems typically apply a sequence of heuristics that reduce these types of flaws in the drawing without guaranteeing to find a drawing with the minimum number of flaws. (en)
- Послойное рисование графа или иерархическое рисование графа — это способ визуализации графов, в котором вершины ориентированного графа рисуются горизонтальными рядами или слоями с рёбрами, преимущественно направленными вниз. Такой способ известен как стиль Сугиямы визуализации графов, по имени Козо Сугиямы, который первым разрабатывал этот стиль. Идеальной формой послойного рисования могло бы быть восходящее планарное рисование, в котором все рёбра ориентированы в одном направлении, и никакая пара рёбер не пересекается. Однако, графы часто содержат циклы, а задача минимизации числа рёбер, направленных в противоположном направлении, NP-трудна, как и задача минимизации числа пересечений. По этой причине системы послойной визуализации графов обычно используют последовательность эвристических подходов, которые уменьшают эти типы изъянов и находят рисунок с минимальным количеством изъянов. (ru)
|
