Diplomová práce

Clustered string representations of graphs

Bc. Dávid Smolka
Anotace

V tejto práci zavádzame (k,m)-klastrované niťové grafy, v ktorých požadujeme, aby niťová reprezentácia bola pokrytá topologickými diskami tak, aby každá niť pretínala nanajvýš k diskov, každý v spojenom úseku, a aby každý disk pretínalo nanajvýš m nití. Vykonávame predbežný výskum tejto modifikovanej definície a rozprávame o tom, ako môžu byť niektoré triedy grafov reprezentované. Taktiež vzájomne …více

Abstract

In this thesis we introduce (k,m)-clustered string graphs, in which we require the string intersection representation to be covered by topological disks in such a way that each string intersects at most k disks, each one in a connected piece, and each disk is intersected by at most m strings. We conduct a preliminary study of this modified definition and discuss how some classes of graphs can be represented …více

Zadání práce
Classical string graphs are the intersection graphs of simple curves in the plane. The student will study the following new modification of this concept: a colection of simple curves (strings) in the plane is (k,m)-clustered if one can cover the representation by topological disks such that every curve intersects at most k disks, each one in a connected piece, and each disk is intersected by at most m curves. A (k,m)-clustered string graph is one having a (k,m)-clustered string representation. The task of the student is to study basic properties of the classes of (k,m)-clustered string graphs, compare these classes for various values of the parameters k,m, to study representability of particular graph types as (k,m)-clustered string graphs, and to try to determine computational complexity of recognition of (some of) these classes of graph.
Práce zkontrolována:
20. 5. 2026 10:12, prof. RNDr. Petr Hliněný, Ph.D., učo 168881
Plný text práce
557 KB / soubor PDF
Jazyk práce
angličtina angličtina
Termín obhajoby
16. 6. 2026
Práce byla úspěšně obhájena

Vedoucí

prof. RNDr. Petr Hliněný, Ph.D., učo 168881
KTP FI MU

Oponent

doc. Mgr. Jan Obdržálek, PhD., učo 1552
KTP FI MU

Konzultant

Mgr. Lukáš Málik, učo 514189
KTP FI MU

Masarykova univerzita Fakulta informatiky
Studijní program
Plán
Diskrétní algoritmy a modely
  • Přidání souboru

    Soubor nebo složku lze nahrát pomocí tlačítka Přidat.
  • Další operace se soubory

    Podrobnosti lze zjistit označením příslušného řádku.
  • Pohled pro experty

    Pro častou práci je možné zvolit režim Více možností.
  • Vyhledávání souborů

    Vyhledávaný výraz můžete zadat přímo do adresního řádku.
  • Rychlý přístup k souborům

    Pomocí funkce Nedávné je možné se rychle vrátit k právě prohlíženým souborům. Oblíbené soubory je také možné označit Hvězdičkou.