Some Characterizations of Three-Directional Orthogonal Ray Graphs

摘要

A graph is called an intersection graph if each vertex correspondsto a unique object such that two vertices are adjacentif and only if the corresponding objects intersect. Aset of such objects is called the representation of the intersectiongraph. Since a set of some practical objects canbe regarded as such a representation, subclasses of intersectiongraphs are studied in various area. An intersectiongraph is called an orthgonal ray graph if the objects in therepresentation of the graph are rays in the plane parallel tox- and y-axes, and no two parallel rays intersect. Clearly,orthogonal ray graph is bipartite. An orthogonal ray graphis called a 3-directional orthogonal ray graph (3DORG)if every vertical ray has the same direction. A 3DORG iscalled a 2-directional orthogonal ray graph (2DORG) ifevery horizontal ray has the same direction.