A characterization of uniquely representable two-directional orthogonal ray graphs
<|reference_start|>A characterization of uniquely representable two-directional orthogonal ray graphs: In this paper, we provide a characterization of uniquely representable two-directional orthogonal ray graphs, which are defined as the intersection graphs of rightward and downward rays. The collection of these rays is called a representation of the graph. Two-directional orthogonal ray graphs are equivalent to several well-studied classes of graphs, including complements of circular-arc graphs with clique cover number two. Normalized representations of two-directional orthogonal ray graphs, where the positions of certain rays are determined by neighborhood containment relations, can be obtained from the normalized representations of circular-arc graphs. However, the normalized representations are not necessarily unique, even when considering only the relative positions of the rays. Recent studies indicate that two-directional orthogonal ray graphs share similar characterizations to interval graphs. Hanlon (1982) and Fishburn (1985) characterized uniquely representable interval graphs by introducing the notion of a buried subgraph. Following their characterization, we define buried subgraphs of two-directional orthogonal ray graphs and prove that their absence is a necessary and sufficient condition for a graph to be uniquely representable.<|reference_end|>
@article{takaoka2024a,
    title={A characterization of uniquely representable two-directional orthogonal
  ray graphs},
    author={Asahi Takaoka},
    journal={arXiv preprint arXiv:2406.06077},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.06077},
    primaryClass={math.CO cs.DM}
}