Original title: Algebraické, strukturální a výpočetní vlastnosti geometrických reprezentací grafů
Translated title: Algebraic, Structural, and Complexity Aspects of Geometric Representations of Graphs
Authors: Zeman, Peter ; Klavík, Pavel (advisor) ; Nešetřil, Jaroslav (referee)
Document type: Master’s theses
Year: 2016
Language: eng
Abstract: Title: Algebraic, Structural and Complexity Aspects of Geometric Representations of Graphs Author: Peter Zeman Department: Computer Science Institute Supervisor: RNDr. Pavel Klavík Supervisor's e-mail: klavik@iuuk.mff.cuni.cz Keywords: automorphism groups, interval graphs, circle graphs, comparability graphs, H-graphs, recognition, dominating set, graph isomorphism, maximum clique, coloring Abstract: We study symmetries of geometrically represented graphs. We describe a tech- nique to determine the automorphism group of a geometrically represented graph, by understanding the structure of the induced action on all geometric representations. We prove that interval graphs have the same automorphism groups as trees, and for a given interval graph, we construct a tree with the same automorphism group which answers a question of Hanlon [Trans. Amer. Math. Soc 272(2), 1982]. For permutation and circle graphs, we give an inductive characterization by semidirect and wreath prod- ucts. We also prove that every abstract group can be realized by the automorphism group of a comparability graph/poset of the dimension at most four. We also study H-graphs, introduced by Biró, Hujter, and Tuza in 1992. Those are intersection graphs of connected subgraphs of a subdivision of a graph H. This thesis is the first comprehensive...
Keywords: automorphism groups; geometric representations of graphs; intersection representations; partial representation extension; geometrické reprezentace grafů; grupy automorfismů; průnikové reprezentace; rozšiřování částečných reprezentací

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/83134

Permalink: http://www.nusl.cz/ntk/nusl-352783


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Master’s theses