Edge Intersection Graphs of Paths on a Triangular Grid

  • Vitor T. F. de Luca UERJ
  • María Pía Mazzoleni UNPL
  • Fabiano S. Oliveira UERJ
  • Jayme L. Szwarcfiter UERJ / UFRJ


We introduce a new class of intersection graphs, the edge intersection graphs of paths on a triangular grid, called EPGt graphs. We compare this new class with the well-known class of EPG graphs. A turn of a path at a grid point is called a bend. An EPGt representation in which every path has at most k bends is called a Bk-EPGt representation and the corresponding graphs are called Bk-EPGt graphs. We characterize the representation of cliques with three vertices and chordless 4-cycles in B1-EPGt representations.

Palavras-chave: Bend number, Edge intersection of paths, Triangular grids


Bertossi, A. A., Pinotti, C. M., Rizzi, R., and Shende, A. M. (2004). Channel assignment for interference avoidance in honeycomb wireless networks. Journal of Parallel and Distributed Computing, 64(12):1329–1344.

Golumbic, M. C. and Jamison, R. E. (1985). The edge intersection graphs of paths in a tree. Journal of Combinatorial Theory, Series B, 38(1):8–22.

Golumbic, M. C., Lipshteyn, M., and Stern, M. (2005). Representations of edge intersection graphs of paths in a tree. DMTCS Proceedings, AE(1):87–92.

Golumbic, M. C., Lipshteyn, M., and Stern, M. (2009). Edge intersection graphs of single bend paths on a grid. Networks: An International Journal, 54(3):130–138.

Janssen, J., Krizanc, D., Narayanan, L., and Shende, S. (1998). Distributed online frequency assignment in cellular networks. In Annual Symposium on Theoretical Aspects of Computer Science, pages 3–13. Springer.

Molitor, P. (1991). A survey on wiring. Elektronische Informationsverarbeitung und Kybernetik, 27(1):3–19.

Zander, J. (2000). Trends in resource management future wireless networks. In 2000 IEEE Wireless Communications and Networking Conference. Conference Record (Cat. No. 00TH8540), volume 1, pages 159–163. IEEE.
Como Citar

Selecione um Formato
LUCA, Vitor T. F. de; MAZZOLENI, María Pía; OLIVEIRA, Fabiano S.; SZWARCFITER, Jayme L.. Edge Intersection Graphs of Paths on a Triangular Grid. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 7. , 2022, Niterói. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2022 . p. 1-4. ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2022.222476.