DIMACS TR: 2004-04
Generalizations of interval-filament graphs
Authors: Fanica Gavril
ABSTRACT
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