New Intersection Graph Hierachies

Abstract

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

String grafy jsou průnikové grafy křivek v rovině. Asinowski a kol. [JGAA 2012] za- definovali hierarchii VPG grafů dle počtů zlomů jednotlivých křivek a ukázali, že tato hierarchie obsahuje právě všechny string grafy. Podobnou hierarchii můžeme pozorovat u k-string grafů: string grafů, jež jsou navíc omezeny tím, že každá dvojice křivek může sdílet nejvýše k bodů. V tomto směru pokračujeme zavedením precisely-k-string grafů, jejichž reprezentace je omezenější, neboť požadujeme, aby každá dvojice křivek sdílela buď právě 0, nebo právě k bodů a zároveň se křivky nesmí jen dotýkat. Dokážeme, že pro každé k ≥ 1 je každý precisely-k-string graf i precisely-(k + 2)-string graf, a že třídy precisely-k-string grafů a precisely-(k + 1)-string grafů jsou inkluzí neporovnatelné. Dále hledáme efektivně reprezentovatelnou třídu průnikových grafů objektů v rovině, která obsahuje všechny grafy s fixním maximálním stupněm. V průběhu zavedeme hi- erarchii průnikových grafů sjednocení d svislých a vodorovných úseček, jež nazýváme impure-d-line grafy, a dalších variant této třídy s omezeními na reprezentaci. Dokážeme, že všechny grafy s maximálním stupněm ≤ 2d jsou impure-d-line grafy a pro d = 1 je toto nejlepší možný výsledek. Také studujeme vztah mezi parametrem d v definici impure-d-line grafů a ostatními grafovými...