An EPG graph G is an edge-intersection graph of paths on a grid. In this
doctoral thesis we will mainly explore the EPG graphs, in particular B1-EPG graphs.
However, other classes of intersection graphs will be studied such as VPG, EPT and
VPT graph classes, in addition to the parameters Helly number and strong Helly
number to EPG and VPG graphs. We will present the proof of NP-completeness
to Helly-B1-EPG graph recognition problem. We investigate the parameters Helly
number and the strong Helly number in both graph classes, EPG and VPG in order
to determine lower bounds and upper bounds for this parameters. We completely
solve the problem of determining the Helly and strong Helly numbers, for Bk-EPG,
and Bk-VPG graphs, for each value k.
Next, we present the result that every Chordal B1-EPG graph is simultaneously
in the VPT and EPT graph classes. In particular, we describe structures that occur
in B1-EPG graphs that do not support a Helly-B1-EPG representation and thus we
define some sets of subgraphs that delimit Helly subfamilies. In addition, features
of some non-trivial graph families that are properly contained in Helly-B1 EPG are
also presented.
|
