Geodesic
On edge-intersection graphs of k-bend paths in grids
Discrete mathematics & theoretical computer science, Tome 12 (2010) no. 1.

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2010_12_1_a1,
     author = {Biedl, Therese and Stern, Michal},
     title = {On edge-intersection graphs of k-bend paths in grids},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {12},
     number = {1},
     year = {2010},
     doi = {10.46298/dmtcs.482},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.482/}
}
TY  - JOUR
AU  - Biedl, Therese
AU  - Stern, Michal
TI  - On edge-intersection graphs of k-bend paths in grids
JO  - Discrete mathematics & theoretical computer science
PY  - 2010
VL  - 12
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.482/
DO  - 10.46298/dmtcs.482
LA  - en
ID  - DMTCS_2010_12_1_a1
ER  - 
%0 Journal Article
%A Biedl, Therese
%A Stern, Michal
%T On edge-intersection graphs of k-bend paths in grids
%J Discrete mathematics & theoretical computer science
%D 2010
%V 12
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.482/
%R 10.46298/dmtcs.482
%G en
%F DMTCS_2010_12_1_a1
Biedl, Therese; Stern, Michal. On edge-intersection graphs of k-bend paths in grids. Discrete mathematics & theoretical computer science, Tome 12 (2010) no. 1. doi : 10.46298/dmtcs.482. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.482/

Cité par Sources :