On edge-intersection graphs of k-bend paths in grids
Therese Biedl, Michal Stern
Abstract
Edge-intersection graphs of paths in grids are graphs that can be
represented such that vertices are paths in a grid and edges between
vertices of the graph exist whenever
two grid paths share a grid edge. This type of graphs is motivated by
applications in conflict resolution of paths in grid networks.
In this paper, we continue the study of edge-intersection graphs of
paths in a grid, which was initiated by Golumbic, Lipshteyn and Stern.
We show that for any k, if the number of bends in each path is restricted to
be at most k, then not all graphs can be represented. Then we study some
graph classes that can be represented with k-bend paths, for small
k.
We show that every planar graph has a representation with 5-bend paths,
every outerplanar graph has a representation with 3-bend paths, and every
planar bipartite graph has a representation with 2-bend paths. We also
study line graphs, graphs of bounded pathwidth, and graphs with
κ-regular edge orientations.
Full Text: PDF PostScript