3D 3 D -interval-filament graphs
Gavril [F. Gavril, Maximum weight independent sets and cliques in intersection graphs of filaments, Inform. Process. Lett. 73 (2000) 181188] defined two new families of intersection graphs: the interval-filament graphs and the subtree-filament graphs. The complements of interval-filament graphs are the cointerval mixed graphs and the complements of subtree-filament graphs are the cochordal mixed graphs. The family of interval-filament graphs contains the families of cocomparability, polygon-circle, circle and chordal graphs. In the present paper we introduce a generalization of the subtree-filament graphs, namely, the 3D 3 D -interval-filament graphs. We prove that the family of 3D-interval-filament graphs, the family of complements of co(interval-filament) mixed graphs and the family of overlap graphs of interval-filaments  are the same, and show that every 3D 3 D -interval-filament graph has an intersection representation by a family of piecewise linear filaments. We use the properties of these graphs to describe an algorithm for maximum weight holes of a given parity in 3D 3 D -interval-filament graphs and an algorithm for antiholes of a given parity in interval-filament and subtree-filament graphs. We define various subfamilies of 3D 3 D -interval-filament graphs and characterize them as overlap graphs and as complements of H H -mixed graphs.
interval-filament graph intersection graph subtree-filament graph overlap graph