6533b7d6fe1ef96bd1267437

RESEARCH PRODUCT

Hierarhisku grafu zīmēšana ar ierobežojumiem

subject

description

Darbā tiek apskatīta grafu hierarhiska zīmēšana ar ierobežojumiem un šo ierobežojumu iekļaušana hierarhiskā grafu zīmēšanas stila realizācijas metodēs. Darbs veltīts grafu zīmēšanas mērķim – attēlot grafu uzskatāmā, viegli uztveramā formā tā, lai grafa struktūra būtu viegli saprotama un attēlotu svarīgākās grafa īpašības. Darbā uzmanība pievērsta vienam no populārākajiem grafu izvietošanas stiliem – hierarhiskajam stilam, kurā virsotnes tiek novietotas horizontālos slāņos. Papildus ņemam vērā, ka ne vienmēr informāciju ir iespējams reprezentēt ar tīras grafu struktūras palīdzību, tāpēc lietotājam var būt nepieciešams definēt kādus īpašus ierobežojumus, kuru rezultātā iegūtais grafa attēls precīzāk atbilst grafa saturam un lietotāja vēlmēm. Tā kā maksimālās saderīgās ierobežojumu apakškopas atrašana vispārīgā gadījumā ir komplicēta problēma, šajā darbā tiek izstrādāts speciāls efektīvs algoritms, kas spēj atrast maksimālo saderīgo ierobežojumu kopu (ar prioritātēm) secīgas virsotņu kopas un virsotņu secības ierobežojumiem. Darbā arī pievērsta uzmanība jautājumiem kā šos ierobežojumus ietvert klasiskajās hierarhiskā stila grafu izvietojuma metodēs.