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

DOI: https://doi.org/10.5753/etc.2022.222476

Resumo

We introduce a new class of intersection graphs, the edge intersection graphs of paths on a triangular grid, called EPG_t 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 EPG_t representation in which every path has at most k bends is called a B_k-EPG_t representation and the corresponding graphs are called B_k-EPG_t graphs. We characterize the representation of cliques with three vertices and chordless 4-cycles in B₁-EPG_t representations.

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

Referências

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.