Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. On edge-intersection ...
Article

On edge-intersection graphs of k-bend paths in grids

Therese Biedl (1), Michal Stern (2)
(1) David R. Cheriton School of Computer Science
(2) Caesarea Rothschild Institute and Department of Computer Science
Download article
Open on HAL
Imported on
March 26, 2015
Published on
January 1, 2010
Last modified on
March 31, 2025
Volume 12
vol. 12:1
DOI
10.46298/dmtcs.482
License
https://about.hal.science/hal-authorisation-v1
Natural Sciences and Engineering Research Council of Canada
Indicators
892
Views
1169
Downloads

On edge-intersection graphs of k-bend paths in grids

Therese Biedl (1), Michal Stern (2)
(1) David R. Cheriton School of Computer Science
(2) Caesarea Rothschild Institute and Department of Computer Science
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.
Keywords
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • Intersection graphs
  • planar graphs
  • graph drawing
Preview
Loading PDF preview...