Premium
Edge intersection graphs of single bend paths on a grid
Author(s) -
Golumbic Martin Charles,
Lipshteyn Marina,
Stern Michal
Publication year - 2009
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20305
Subject(s) - combinatorics , grid , mathematics , graph , enhanced data rates for gsm evolution , intersection (aeronautics) , discrete mathematics , path (computing) , computer science , telecommunications , geometry , engineering , programming language , aerospace engineering
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 be a collection of nontrivial simple paths on a grid . We define the edge intersection graph E P G () of to have vertices which correspond to the members of , such that two vertices are adjacent in E P G () if the corresponding paths in share an edge in . An undirected graph G is called an edge intersection graph of paths on a grid (EPG) if G = E P G () for some and , and 〈,〉 is an EPG representation of G . We prove that every graph is an EPG graph. A turn of a path at a grid point is called a bend. We consider here 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 one to generate non B 1 ‐EPG graphs. Furthermore, we characterize the representation of cliques and chordless 4‐cycles in B 1 ‐EPG graphs. We also prove that single bend paths on a grid have Strong Helly number 3. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009