论文标题
三角网格上路径的边缘交点图
Edge Intersection Graphs of Paths on a Triangular Grid
论文作者
论文摘要
我们介绍了一类新的相交图，即三角网格上的路径的边缘交点图，称为EPGT图。我们显示了从这个新类到众所周知的EPG图类别的相似性和差异。在网格点处的路径转弯称为弯曲。每个路径最多具有$ k $ bends的EPGT表示形式称为a b $ _k $ -epgt表示，相应的图称为b $ _K $ -EPGT图。我们提供了b $ _ {2} $ - epg图的示例，该图为b $ _ {1} $ - epgt。我们表征了三个顶点的表示集团的表示形式和B $ _ {1} $ - EPGT表示中的无弦的4循环。我们还证明b $ _ {1} $ - EPGT图具有强的Helly Number $ 3 $。此外，我们证明b $ _ {1} $ - EPGT图是$ 7 $ -clique colorable。
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.
