标题： 线段不交图的互可见性${\mathbb R}^2$ 显示英文标题

标题： Mutual-visibility of the disjointness graph of segments in ${\mathbb R}^2$

摘要： 设 $G=(V(G),E(G))$ 为一个简单图，并令 $U\subseteq V(G)$。 两个不同的顶点$x,y\in U$在$U$-互可见的条件是$G$包含一条最短的$x$-$y$路径，并且该路径内部与$U$不相交。 称$U$是$G$的一个互可见集，如果$U$中任意两个顶点是$U$-互可见的。 $G$的互可见数$\mu(G)$是$G$的最大互可见集的大小。 设 $P$ 是 ${\mathbb R}^2$ 中一般位置的 $n\geq 3$ 个点的集合。 线段 $D(P)$ 的不相交图 $P$ 是这样一个图，其顶点是所有以 $P$ 中的点为端点的闭直线段，其中两条线段当且仅当它们不相交时在 $D(P)$ 中相邻。 本文给出了$\mu(D(P))$的紧的上下界，并且证明几乎所有边不交图的直径为 2。 显示英文摘要

摘要： Let $G=(V(G),E(G))$ be a simple graph, and let $U\subseteq V(G)$. Two distinct vertices $x,y\in U$ are $U$-mutually visible if $G$ contains a shortest $x$-$y$ path that is internally disjoint from $U$. $U$ is called a mutual-visibility set of $G$ if any two vertices of $U$ are $U$-mutually visible. The mutual-visibility number $\mu(G)$ of $G$ is the size of a largest mutual-visibility set of $G$. Let $P$ be a set of $n\geq 3$ points in ${\mathbb R}^2$ in general position. The disjointness graph of segments $D(P)$ of $P$ is the graph whose vertices are all the closed straight line segments with endpoints in $P$, two of which are adjacent in $D(P)$ if and only if they are disjoint. In this paper we establish tight lower and upper bounds for $\mu(D(P))$, and show that almost all edge disjointness graphs have diameter 2.