论文标题
在$ k $ - 弯曲和单调$ \ ell $ - 弯曲的边缘交叉图上的路径图
On $k$-Bend and Monotonic $\ell$-Bend Edge Intersection Graphs of Paths on a Grid
论文作者
论文摘要
如果图$ g $可以通过网格上的路径表示，则$ g $的每个顶点对应于网格上的一个路径，而当相应的路径共享网格边缘时，$ g $的两个顶点才相邻，则此图称为EPG，该图称为EPG，并且表示为EPG表示。 $ k $键入的EPG表示是EPG表示，每条路径最多都有$ k $ bends。所有具有$ K $ bend EPG表示的图表的类均由$ b_k $表示。 $ b_ \ ell^m $是所有具有单调$ \ ell $ - 弯曲EPG表示的图表的类，即$ \ ell $ - bend $ - 弯曲EPG表示，其中每个路径在列和行中都上升。 $ b^m_k \ subseteq b_k $的所有$ k $都是微不足道的。此外，众所周知，$ b^m_k \ subsetneqq b_k $，$ k = 1 $。通过调查$ b_k $ -membership和$ b^m_k $ - 完整的两部分图的会员，我们证明，包含在\ in \ {2,3,5 \} $中，对于$ k \ in \ k \ geqslant 7 $。特别是，我们得出了该会员资格的必要条件，这些条件必须通过$ m $，$ n $和$ k $来实现，其中$ m $和$ n $是两部分图的两个分区类中的顶点数量。我们推测$ b_ {k}^{m} \ subsetNeqq b_ {k} $也持有$ k \ in \ {4,6 \} $。 此外，我们表明$ b_k \ not \ subseteq b_ {2k-9}^m $ hold tor All $ k \ geqslant 5 $。这意味着限制路径的形状会导致EPG表示中所需的弯曲数量显着增加。到目前为止，该增加的数量尚无范围。我们证明$ b_1 \ subseteq b_3^m $保留，提供了这种结果的第一个结果。
If a graph $G$ can be represented by means of paths on a grid, such that each vertex of $G$ corresponds to one path on the grid and two vertices of $G$ are adjacent if and only if the corresponding paths share a grid edge, then this graph is called EPG and the representation is called EPG representation. A $k$-bend EPG representation is an EPG representation in which each path has at most $k$ bends. The class of all graphs that have a $k$-bend EPG representation is denoted by $B_k$. $B_\ell^m$ is the class of all graphs that have a monotonic $\ell$-bend EPG representation, i.e. an $\ell$-bend EPG representation, where each path is ascending in both columns and rows. It is trivial that $B^m_k\subseteq B_k$ for all $k$. Moreover, it is known that $B^m_k\subsetneqq B_k$, for $k=1$. By investigating the $B_k$-membership and the $B^m_k$-membership of complete bipartite graphs we prove that the inclusion is also proper for $k\in \{2,3,5\}$ and for $k\geqslant 7$. In particular, we derive necessary conditions for this membership that have to be fulfilled by $m$, $n$ and $k$, where $m$ and $n$ are the number of vertices on the two partition classes of the bipartite graph. We conjecture that $B_{k}^{m} \subsetneqq B_{k}$ holds also for $k\in \{4,6\}$. Furthermore, we show that $B_k \not\subseteq B_{2k-9}^m$ holds for all $k\geqslant 5$. This implies that restricting the shape of the paths can lead to a significant increase of the number of bends needed in an EPG representation. So far no bounds on the amount of that increase were known. We prove that $B_1 \subseteq B_3^m$ holds, providing the first result of this kind.
