|
|
New Intersection Graph Hierachies
Chmel, Petr ; Jelínek, Vít (advisor) ; Kratochvíl, Jan (referee)
String graphs are the intersection graphs of curves in the plane. Asinowski et al. [JGAA 2012] introduced a hierarchy of VPG graphs based on the number of bends and showed that the hierarchy contains precisely all string graphs. A similar hierarchy can be observed with k-string graphs: string graphs with the additional condition that each pair of curves has at most k intersection points. We continue in this direction by introducing precisely-k-string graphs which restrict the representation even more so that each pair of curves has either 0 or precisely k intersection points with all of them being crossings. We prove that for each k ≥ 1, any precisely-k-string graph is a precisely-(k + 2)-string graph and that the classes of precisely-k-string graphs and precisely-(k + 1)-string graphs are incomparable with respect to inclusion. We also investigate the problem of finding an efficiently representable class of intersec- tion graphs of objects in the plane that contains all graphs with fixed maximum degree. In the process, we introduce a new hierarchy of intersection graphs of unions of d hori- zontal or vertical line segments, called impure-d-line graphs, and other variations of the class with representation restrictions. We prove that all graphs with maximum degree ≤ 2d are impure-d-line graphs and for d = 1...
|
|
|
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.
|
|
| |
guest ::
RSS feed.