Rutgers New Brunswick/Piscataway Campus
ADD TITLE HERE
 

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.

Finding people and more... Rutgers New Brunswick/Piscataway Campus