Brown Bag Seminar - March 12, 2006
Speaker: Martin C. Golumbic
Affiliation: The Caesarea Rothschild Institute, University of Haifa, Israel.
Title: Edge intersection graphs of single bend paths on a grid.
Time: 12:00 - 1:00 PM
Location: RUTCOR Building - Lounge, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
We combine the known notion of the edge intersection graphs of paths
in a tree with a VLSI grid layout model to introduce the edge
intersection graphs of paths on a grid.
Let $\cal{P}$ be a collection of nontrivial simple paths on a grid
$\cal{G}$. We define the edge intersection graph $EPG(\cal{P})$ of
$\cal{P}$ to have vertices which correspond to the members of
$\cal{P}$, such that two vertices are adjacent in $EPG(\cal{P})$ if
the corresponding paths in $\cal{P}$ share an edge in $\cal{G}$. An
undirected graph $G$ is called \textit{an edge intersection graph of
paths on a grid} (EPG) if $G$ = $EPG(\mathcal{P})$ for some
$\mathcal{P}$ and $\cal{G}$, and \PG is an EPG representation of
$G$. We prove that any graph is an EPG graph.
A turn of a path at a grid point is called a bend. We
consider here only EPG representations in which every path has at
most a single bend, called B$_1$-EPG representations and the
corresponding graphs are called B$_1$-EPG graphs. We prove that any
tree is a B$_1$-EPG graph. Moreover, we give a structural property
that enables to generate non B$_1$-EPG graphs. Consequently, some of
well-known graphs appear to be non B$_1$-EPG graphs.
Furthermore, we characterize the representation of cliques and
chordless 4-cycles in B$_1$-EPG graphs.
Back to Seminars Page.
Back to RUTCOR homepage.
|