|
|
Geometrické reprezentace grafů
Klavík, Pavel ; Kratochvíl, Jan (advisor) ; Pergel, Martin (referee)
Intersection graphs are a well studied field of graph theory. Complexity questions of recognition have been studied for several years. Given a graph, we ask whether the graph belongs to a fixed class. In this thesis, we introduce a new problem of partial representation extension. In this problem, aside from a graph, a part of a representation is also fixed. We ask whether it is possible to extend this partial representation to the whole graph. This problem is at least as hard as recognition. We study the partial representation extension problem for several intersection defined classes. We solve extending of interval graphs in time O(n2) and proper interval graphs in time O(mn). Using an approach described by Golumbic, we further show that comparability and permutation graphs are extendable in time O( · m). There are some classes that are known to be equal, for example unit interval graphs and proper interval graphs. Surprisingly, in the case of extending, we need to distinguish them. Similarly, we show that extending of function graphs and extending of co-comparability graphs are completely different problems.
|
guest ::
RSS feed.