A \emph{chord} in a cycle is an edge that is not part of the cycle but connects two vertices of the cycle. A graph is \emph{chordal} if all its cycles of four or more vertices have a chord. A graph is \emph{strongly chordal} if it is chordal, and every cycle of even length larger than $6$ has an odd chord (a chord that connects two vertices that are an odd distance apart in the cycle). In this work, we show that a graph is strongly chordal if and only if it has an intersection representation by unit balls in a \emph{real tree} (a metric space with a tree-like structure), or equivalently, by proper balls, or arbitrary balls. These characterizations of strongly chordal graphs find their motivation in the \emph{Sitting Closer to Friends than Enemies} (SCFE) problem. A signed graph is a graph with a sign assignment to its edges. The SCFE problem is to find an injection of the vertex set of a given signed graph into a metric space such that, for every pair of incident edges with different signs, the end vertices of the positive edge are injected closer in the space than the end vertices of the negative edge. Such an injection is called a \emph{valid distance drawing}. Using the characterization for strongly chordal graphs, we show that a complete signed graph has a valid distance drawing in a real tree if, and only if, its subgraph composed of all (and only) its positive edges is strongly chordal.

Thanks. We have received your report. If we find this content to be in
violation of our guidelines,
we will remove it.

Ok