Nové hierarchie průnikových grafů

Chmel, Petr

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...

host :: přihlásit Digitální repozitář
		Hledej		Nový záznam		Nápověda		O repozitáři