
Algorithmic aspects of intersection representations
Chmel, Petr ; Jelínek, Vít (advisor) ; Kratochvíl, Jan (referee)
As some problems are (NP)hard to solve in the general case, a possible approach is to try to solve the problem on a restricted class of graphs. In the thesis, we focus on graphs induced by axisaligned Lshapes, socalled Lgraphs, and a similar class of axis aligned Lshapes and Lshapes, referred to as {L, L}graphs, with two vertices sharing an edge if and only if their respective curves intersect. We show that recognizing both L graphs and {L, L}graphs is NPcomplete. The second part of the thesis focuses on other typical decision problems on Lgraphs and their relatives: finding the clique number, the independence number or a 3coloring.


Algorithmic aspects of intersectiondefined graph classes
Jedličková, Nikola ; Kratochvíl, Jan (advisor) ; Fiala, Jiří (referee)
Geometrically representable graphs are extensively studied area of research in contempo rary literature due to their structural characterizations and efficient algorithms. The most frequently studied class of such graphs is the class of interval graphs. In this thesis we focus on two problems, generalizing the problem of recognition, for classes related to interval graphs. In the first part, we are concerned with adjusted interval graphs. This class has been studied as the right digraph analogue of interval graphs. For interval graphs, there are polynomial algorithms to extend a partial representation by given intervals into a full interval representation. We will introduce a similar problem  the partial ordering extension  and we will provide a polynomial algorithm to extend a partial ordering of adjusted interval digraphs. In the second part, we show two NPcompleteness results regarding the simultaneous representation problem, introduced by Lubiw and Jampani. The simultaneous representation problem for a given class of intersection graphs asks if some k graphs can be represented so that every vertex is represented by the same object in each representation. We prove that it is NPcomplete to decide this for the class of interval and circulararc graphs in the case when k is a part of the input and graphs...


Computational and structural apects of interval graphs and their variants
Novotná, Jana ; Kratochvíl, Jan (advisor) ; Jelínek, Vít (referee)
Interval graphs, intersection graphs of segments on a real line (intervals), play a key role in the study of algorithms and special structural properties. Unit interval graphs, their proper subclass, where each interval has a unit length, has also been extensively studied. We study mixed unit interval graphsa generalization of unit interval graphs where each interval has still a unit length, but intervals of more than one type (open, closed, semiclosed) are allowed. This small modification captures a much richer class of graphs. In particular, mixed unit interval graphs are not clawfree, compared to unit interval graphs. Heggernes, Meister, and Papadopoulos defined a representation of unit interval graphs called the bubble model which turned out to be useful in algorithm design. We extend this model to the class of mixed unit interval graphs. The original bubble model was used by Boyaci, Ekim, and Shalom for proving the polynomiality of the MaxCut problem on unit interval graphs. However, we found a significant mistake in the proof which seems to be hardly repairable. Moreover, we demonstrate advantages of such model by providing a subexponentialtime algorithm solving the MaxCut problem on mixed unit interval graphs using our extended version of the bubble model. In addition, it gives us a polynomialtime...


Circle packing and Möbius transformations
Porvichová, Janka ; Zeman, Peter (advisor) ; Kratochvíl, Jan (referee)
A graph can be represented by various geometric representations. In this work we focus on the circle packing representation. We state various concepts impor tant for proving results regarding this kind of representation. We introduce a known proof of existence of a circle packing for planar graphs and a proof of existence of a primaldual circle packing for 3connected graphs. Next, we focus on computational complexity of extending the representation for a given partial circle packing. We examine the proof of the theorem stating that deciding whet her such an extension exists is an NPhard problem. We introduce our theoretical algorithm for extension construction based on real RAM machine. 1


Computational complexity in graph theory
Melka, Jakub ; Kratochvíl, Jan (advisor) ; Fiala, Jiří (referee)
In the present work we study the problem of reconstructing a graph from its closed neighbourhood list. We will explore this problem, formulated by V. Sós, from the point of view of the fixed parameter complexity. We study the graph reconstruction problem in a more general setting, when the reconstructed graph is required to belong to some special graph class. In the present work we prove that this general problem lies in the complexity class FPT, when parametrized by the treewidth and maximum degree of the reconstructed graph, or by the number of certain special induced subgraphs if the reconstructed graph is 2degenerate. Also, we prove that the graph reconstruction problem lies in the complexity class XP when parametrized by the vertex cover number. Finally, we prove mutual independence of the results

 
 

Physiological mechanisms of abiotic stress tolerance in Sorghum bicolor
Kratochvíl, Jan ; Konrádová, Hana (advisor) ; Lhotáková, Zuzana (referee)
Current agriculture is facing a serious challenge of decreasing precipitation and irregular occurrence of drought periods including their unfavorable distribution during the vegetation season. This leads to growing interest in planting highly droughtresistant crops like sorghum. In comparison with other crops, sorghum excels in low water demand, though exhibits high susceptibility to low temperatures, which hampers its spread to new regions. Surprisingly, there is not enough information about the nature of sorghum's reaction to cold exposure. The aim of this diploma thesis was to describe reactions of young sorghum plants exposed to cold stress, low water availability and their combination and to verify the possibility of plant hardening through previous lowstress load. The special focus was paid to changes in carbohydrate metabolism, which plays generally very important role in plant defense reactions. The other analyzed physiological traits were leaf tissue osmotic potential, proline content and basic morphometric characteristics. Experimental design consisted of pot experiments conducted in growth chambers and the experiments performed under controlled conditions in vitro, using two sorghum genotypes "Ruzrok" and "01Z1800012". Both genotypes exhibited similar response to stress treatment....


Highdensity, Lowrise housing in Brno, Černá Pole
Kuba, Jonáš ; Kratochvíl, Jan (referee) ; Májek, Jan (advisor)
The aim of the thesis is to design a compact housing with appropriate public services in the current barracks area in Černá Pole which is 16.97 ha large. The project respects existing buildings as it continues with a block structure of urban rental houses. The result is the area unification and creating a new local centre. The project strives for a functional urban development as it emphasizes the concept functionality, clarity and purity.


Highdensity, Lowrise housing in Brno, Černá Pole
Janík, Tobiáš ; Kratochvíl, Jan (referee) ; Májek, Jan (advisor)
Subject of my diploma thesis is to design new residential neighborhood on sight currently occupied by Barracks in Brno, Černá Pole. It is little used in the moment and forms spacial barrier in city organism and is slowly detracting. New proposal integrates area into surrounding development and is trying to maximally utilize its positive aspects. On site is not proposed just quiet residential neighborhood, but also city hall, shops, college dorm, primary school and kindergarten, creating a balanced unit communicating with the surrounding area.
