Обзорное представление

Материал из WEGA
Перейти к навигации Перейти к поиску

Обзорное представление (visibility representation) [math]\displaystyle{ \Gamma }[/math] – такое его изображение заданного st-графа [math]\displaystyle{ G }[/math], в котором каждая вершина [math]\displaystyle{ p }[/math] представлена горизонтальным отрезком [math]\displaystyle{ \Gamma(p) }[/math], называемым вершинным отрезком, а каждая дуга [math]\displaystyle{ (p, q) }[/math] — вертикальным отрезком [math]\displaystyle{ \Gamma(p, q) }[/math], называемым реберным отрезком, таким образом, что справедливы следующие три свойства: вершинные отрезки не накладываются друг на друга, реберные отрезки не накладываются друг на друга, реберный отрезок [math]\displaystyle{ \Gamma(p, q) }[/math] имеет нижнюю границу, лежащую на [math]\displaystyle{ \Gamma(p) }[/math], и верхнюю границу, лежащую на [math]\displaystyle{ \Gamma(q) }[/math], и не пересекает ни один другой вершинный отрезок.

Обзорное представление планарного st-графа [math]\displaystyle{ G }[/math] может быть построено из мозаичного представления графа [math]\displaystyle{ G }[/math] с вырожденными плитками для вершин и невырожденными плитками для граней.

Литература

  • Касьянов В. Н., Евстигнеев В. А. Графы в программировании: обработка, визуализация и применение. – СПб.: БХВ-Петербург, 2003. – 1104 c.
  • Касьянов В.Н., Касьянова Е.В. Визуализация информации на основе графовых моделей // Научная визуализация. – 2014. – Том. 6, N 1. – С. 31 – 50.
  • Касьянов В.Н., Касьянова Е.В. Визуализация информации на основе графовых моделей. – Новосибирск: НГУ, 2014. – 149 с.