|
| |
|
|
Computational complexity in Graph Theory
Herman, Jan ; Kratochvíl, Jan (advisor) ; Flusser, Jan (referee)
Seidel's switching is a graph operation , which for a given graph G and one of its vertices v gives the graph derived from G by replacing edges adjacent to v by non-edges and vice-versa. A graph H is called a switch of G, if H can be obtained from G by a sequence of switches of its vertices. In the thesis we introduce known results ab out computational complexity of problems if for a given graph G t here exists its switching lying in a given graph class (}. For different graph classes g, we later study a characterization of the class of all graphs, which can be switched into g, in terms of minimal forbidden induced subgraphs. We introduce a full characterization of a class of graphs switchable to a disjoint union af cutworms, respectively partial pairings by forbidden subgraphs. We also prove that a class of graphs switchable to chordal has infinit ely many non-isomorphic forbidden subgraphs. At the end we deal with the relationship between swit ching and other graph operations and graph classes operations.
|
|
|
Drawing geometric graphs on red-blue point sets
Soukup, Jan ; Kynčl, Jan (advisor) ; Kratochvíl, Jan (referee)
Consider a set B of blue points and a set R of red points in the plane such that R ∪ B is in general position. A graph drawn in the plane whose edges are straight-line segments is called a geometric graph. We investigate the problem of drawing non-crossing properly colored geometric graphs on the point set R ∪ B. We show that if ||B| − |R|| ≤ 1 and a subset of R forms the vertices of a convex polygon separating the points of B, lying inside the polygon, from the rest of the points of R, lying outside the polygon, then there exists a non-crossing properly colored geometric path on R∪B covering all points of R ∪ B. If R∪B lies on a circle, the size of the longest non-crossing geometric path is related to the size of the largest separated matching; a separated matching is a non-crossing properly colored geometric matching where all edges can be crossed by a line. A discrepancy of R ∪ B is the maximal difference between cardinalities of color classes of intervals on the circle. When the discrepancy of R ∪ B is at most 2, we show that there is a separated matching covering asymptotically 4 5 of points of R ∪ B. During this proof we use a connection between separated matchings and the longest common subsequences between two binary sequences where the symbols correspond to the colors of the points.
|
|
|
Partial representation extension for subclasses of interval graphs
Onduš, Daniel ; Kratochvíl, Jan (advisor) ; Jelínek, Vít (referee)
The problem of extending partial representations for an interval graph asks, whether it is possible to extend a given representation of some vertices to a valid representation of the entire graph. In this thesis we extend the recent result of Klavík et al. who proved REPEXT can be decided for proper and unit interval graphs in polynomial time. We describe properties of PI± and U± graphs and their representations and present algorithms deciding REPEXT for these classes in polynomial time. In the process, we characterize relations between the K1,3's in a graph and show that we can decide the open vertex of every K1,3. We also define notions of representation of the same order type and locally similar representations as well as intervals forced and locally forced to be closed (open) that are essential for extending partial representations when multiple types of intervals can occur in the same representation. We characterize intervals forced and locally forced to be closed (open) in a U± graph using integer gaps in the pre-representation and we construct lower bounds for the rightmost endpoint of a component in polynomial time.
|
|
|
Namesti Miru in Brno improvement and completion
Mikel, Jakub ; Štěpánek, Martin (referee) ; Kratochvíl, Jan (advisor)
Form and future utilization of Brno square Míru is on a long-term basis discussed topic for the general and the professional public. The discussion on the utilization of this significant area was accelerated after the Ministry of Defence transferred the possession of the unused military area to city of Brno in 2003. The residents of the Masaryk´s district, of which is the square Míru notional centre, have written many protest petitions and have held several meetings with suggesting outputs for municipal political authorities. Currently held urbanistic-architectural public tender, of which the results are to be announced in the term corresponding with the date of submission of this bachelor thesis, will be interesting confrontation of the students´ theses. The bachelor thesis will check student´s knowledge in the fields of designing public city areas, designing poly-functional buildings, interior design and technological and constructional solutions.
|
|
|
Namesti Miru in Brno improvement and completion
Juříček, Pavel ; Štěpánek, Martin (referee) ; Kratochvíl, Jan (advisor)
The appearance of Namesti Miru has been unsuitable for a long time with many functional and aesthetic problems. The proposal addresses the use of public space and transforms it into a dignified square, which forms the heart of the Masaryk district. At the same time, the project combines the functionality of the transport hub with the maximum use of public space. The building in the southern part of the square responds to the demands of the inhabitants and accommodates both administrative and residential functions and the cultural activities of visitors. The building creates a semi-public space with plenty of greenery. The architectural and urban design of the building responds to the surrounding area and refers to the history of the Masaryk district.
|
|
|
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 axis-aligned L-shapes, so-called L-graphs, and a similar class of axis- aligned L-shapes and L-shapes, 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 NP-complete. The second part of the thesis focuses on other typical decision problems on L-graphs and their relatives: finding the clique number, the independence number or a 3-coloring.
|
|
|
Algorithmic aspects of intersection-defined 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 NP-completeness 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 NP-complete to decide this for the class of interval and circular-arc 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 graphs-a generalization of unit interval graphs where each interval has still a unit length, but intervals of more than one type (open, closed, semi-closed) are allowed. This small modification captures a much richer class of graphs. In particular, mixed unit interval graphs are not claw-free, 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 subexponential-time algorithm solving the MaxCut problem on mixed unit interval graphs using our extended version of the bubble model. In addition, it gives us a polynomial-time...
|
|
|
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 primal-dual circle packing for 3-connected 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 NP-hard problem. We introduce our theoretical algorithm for extension construction based on real RAM machine. 1
|
guest ::
RSS feed.