episciences.org_482_20230320164448801
20230320164448801
episciences.org
raphael.tournoy+crossrefapi@ccsd.cnrs.fr
episciences.org
Discrete Mathematics & Theoretical Computer Science
13658050
01
01
2010
Vol. 12 no. 1
On edgeintersection graphs of kbend paths in grids
Therese
Biedl
Michal
Stern
Edgeintersection 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 edgeintersection 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 kbend paths, for small k. We show that every planar graph has a representation with 5bend paths, every outerplanar graph has a representation with 3bend paths, and every planar bipartite graph has a representation with 2bend paths. We also study line graphs, graphs of bounded pathwidth, and graphs with regular edge orientations.
01
01
2010
482
Natural Sciences and Engineering Research Council of Canada
https://hal.science/hal00990425v1
10.46298/dmtcs.482
https://dmtcs.episciences.org/482

https://dmtcs.episciences.org/482/pdf

https://dmtcs.episciences.org/482/pdf