DIMACS TR: 2004-04

Generalizations of interval-filament graphs

Authors: Fanica Gavril


Let $I$ be a family of intervals on a line $L$ in a plane $PL$ such that every two intersecting intervals have a common segment. Let $V=\{v| i(v)\in I\}$ be a vertex set. In $PL$, above L, construct to each interval $i(v)\in I$ a filament (curve) $a(v)$ connecting its two endpoints and bounded in $PL$ by the endpoints of $i(v)$; $FI=\{a(v)| i(v)\in I\}$ is a family of $2D-interval-filaments$ and its intersection graph is a $2D-interval-filament graph$ [GA4]. Let $PP$ be a plane perpendicular to $PL$ whose intersection with $PL$ is exactly the family of $2D-interval-filaments$ $FI$. In $PP$, above $PL$, for every $a(v)\in FI$, connect its endpoints by a filament $v$ such that if $a(u)$,$a(v)$ overlap the two filaments $u$,$v$ intersect and if $a(u)$,$a(v)$ are disjoint, the two filaments $u,v$ do not intersect; $FF=\{v| a(v)\in FI\}$ is a family of $3D-interval-filaments$ and its intersection graph is a $3D-interval-filament graph$. A graph $G(V,E)$ is $G$ $mixed$ if its edge set can be partitioned into two disjoint subsets $E1$, $E2$ such that $G(V,E1)\in G$, $G(V,E2)$ is transitive and for every three vertices $u,v,w$ if $u\rightarrow v\in E2$ and $(v,w)\in E1$ then $(u,w)\in E1$.

We prove that emph{the family of complements of 3D-interval-filament graphs is exactly the family of co(2D-interval-filament) mixed graphs} and define various subfamilies of $3D$-interval-filament graphs characterizing them as complements of families of G mixed graphs. We present another generalization of the $2D$-interval-filament graphs, namely the $k-filament graphs$. We describe polynomial time algorithms for holes in co(G mixed) graphs.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2004/2004-04.ps.gz

DIMACS Home Page