๐ฎ
๐ฎ
The Ethereal
Edge Intersection Graphs of Paths on a Triangular Grid
March 08, 2022 ยท The Ethereal ยท ๐ Anais do VII Encontro de Teoria da Computaรงรฃo (ETC 2022)
"No code URL or promise found in abstract"
Evidence collected by the PWNC Scanner
Authors
Vitor T. F. de Luca, Marรญa Pรญa Mazzoleni, Fabiano S. Oliveira, Tanilson D. Santos, Jayme L. Szwarcfiter
arXiv ID
2203.04250
Category
cs.DM: Discrete Mathematics
Cross-listed
cs.DS
Citations
1
Venue
Anais do VII Encontro de Teoria da Computaรงรฃo (ETC 2022)
Last Checked
5 months ago
Abstract
We introduce a new class of intersection graphs, the edge intersection graphs of paths on a triangular grid, called EPGt graphs. We show similarities and differences from this new class to 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 B$_k$-EPGt representation and the corresponding graphs are called B$_k$-EPGt graphs. We provide examples of B$_{2}$-EPG graphs that are B$_{1}$-EPGt. We characterize the representation of cliques with three vertices and chordless 4-cycles in B$_{1}$-EPGt representations. We also prove that B$_{1}$-EPGt graphs have Strong Helly number $3$. Furthermore, we prove that B$_{1}$-EPGt graphs are $7$-clique colorable.
Community Contributions
Found the code? Know the venue? Think something is wrong? Let us know!
๐ Similar Papers
In the same crypt โ Discrete Mathematics
๐ฎ
๐ฎ
The Ethereal
An Introduction to Temporal Graphs: An Algorithmic Perspective
๐ฎ
๐ฎ
The Ethereal
Guarantees for Greedy Maximization of Non-submodular Functions with Applications
๐ฎ
๐ฎ
The Ethereal
A note on the triangle inequality for the Jaccard distance
๐ฎ
๐ฎ
The Ethereal
Fast clique minor generation in Chimera qubit connectivity graphs
๐ฎ
๐ฎ
The Ethereal