Název:
Průnikové reprezentace grafů
Překlad názvu:
Intersection representations of graphs
Autoři:
Töpfer, Martin ; Jelínek, Vít (vedoucí práce) ; Šámal, Robert (oponent) Typ dokumentu: Bakalářské práce
Rok:
2015
Jazyk:
cze
Abstrakt: [cze][eng] Průnikový graf je graf, ve kterém mezi dvěma vrcholy vede hrana, právě když jim odpovídající objekty se protínají. Tato práce se zabývá průnikovými grafy L-útvarů (tzv. L-grafy) a jejich speciálním případem, kdy konce všech L-útvarů jsou na jedné přímce (tzv. vnějškovými L-grafy). Po přehledu, co platí o L-grafech, používáme podobné postupy na vnějškové L-grafy. Ukážeme, že intervalové grafy, tětivové grafy (circular graphs) a vnějškově rovinné grafy jsou vnějškové L-grafy. Poté charakterizujeme vnějškové L-grafy pomocí uspořádání vrcholů bez zakázaných vzorů. Powered by TCPDF (www.tcpdf.org)We investigate intersection graphs of axis-aligned L-shapes (L-graphs) and their subclass, when all L- shapes have one of their endpoints on the same line - let us call this class outer-L-graphs. In the beginning we introduce some known facts about L-graphs. Then we show, that interval, circular and outerplanar graphs are subclasses of outer-L-graphs. We also characterise outer-L-graphs using ordering without forbidden patterns. Powered by TCPDF (www.tcpdf.org)
Klíčová slova:
Bk-VPG grafy; L-grafy; průnikové grafy; rovinné grafy; Bk-VPG; intersection graphs; L-graphs; L-shape; outer-string