Technical Report CS-2006-17

TR#:CS-2006-17
Class:CS
Title: 3D-Interval-Filament Graphs
Authors: Fanica Gavril
PDFCS-2006-17.pdf
Abstract: Gavril [GA4] 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 new family of intersection graphs, the 3D-interval-filament graphs, which are a generalization of the subtree-filament graphs. We prove that the family of complements of 3D-interval-filament graphs is exactly the family of co(interval-filament) mixed graphs and every 3D-interval-filament graph has an intersection representation by a family of piecewise linear filaments. We define various subfamilies of 3D-interval-filament graphs characterized as complements of families of G-mixed graphs.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2006/CS/CS-2006-17), rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 2006
To the main CS technical reports page

Computer science department, Technion
admin