Citation
Circular-arc graphs

Material Information

Title:
Circular-arc graphs
Creator:
Byers, Ronald Ellis
Publication Date:
Language:
English
Physical Description:
137 leaves : illustrations ; 28 cm

Thesis/Dissertation Information

Degree:
Master's ( Master of science)
Degree Grantor:
University of Colorado Denver
Degree Divisions:
Department of Mathematical and Statistical Sciences, CU Denver
Degree Disciplines:
Mathematics

Subjects

Subjects / Keywords:
Graph theory ( lcsh )
Graph theory ( fast )
Genre:
bibliography ( marcgt )
theses ( marcgt )
non-fiction ( marcgt )

Notes

Bibliography:
Includes bibliographical references (leaves 135-137).
General Note:
Submitted in partial fulfillment of the requirements for the degree, Master of Science, Department of Mathematical and Statistical Sciences
Statement of Responsibility:
by Ronald Ellis Byers.

Record Information

Source Institution:
|University of Colorado Denver
Holding Location:
Auraria Library
Rights Management:
All applicable rights reserved by the source institution and holding location.
Resource Identifier:
19817942 ( OCLC )
ocm19817942
Classification:
LD1190.L62 1988m .B885 ( lcc )

Full Text
CIRCULAR-ARC GRAPHS
by
Ronald Ellis Byers
B.A., Pillsbury Baptist Bible College, 1970
M.Div., Baptist Bible College of Denver, 1973
B.A., Metropolitan State College, 1979
A thesis submitted to the
Faculty of the Graduate School of the
University of Colorado in partial fulfillment
of the requirements for the degree of
Master of Science
Department of Mathematics
1988


This thesis for the Master of Science degree by
Ronald Ellis Byers
has been approved for the
Department of
Mathematics
by
Date At>c\\ ;


Byers, Ronald Ellis (M.S., Applied Mathematics)
CircularArc Graphs
Thesis directed by Assistant Professor Jennifer M.
Ryan
A graph G is a circular-arc graph if there
is a one-to-one correspondence between the
vertices of G and a family of arcs on a circle
such that two distinct vertices are adjacent when
the corresponding arcs intersect.
Five characterizations of circulararc
graphs are given in this paper, using ideas such
as circular -1's, quasi-circular l's, consecutive
l's, circularly compatible lrs, and the augmented
adjacency matrix.
An interval graph is one type of circular-
arc graph presented here and is the intersection
graph of a family of intervals on a line. Its
vertex-maximal clique incidence matrix has
consecutive l's, which can be demonstrated using
the Fulkerson-Gross algorithm. Proper interval
graphs have no interval properly contained in
another. Unit interval graphs have intervals of
unit length and happen to coincide with proper
interval graphs.


IV
Two more kinds of circular-arc graphs
discussed are proper and unit circular-arc graphs.
Proper circular-arc graphs have no arcs properly
contained in any other. Unit circular-arc graphs
Eire a subset of proper circulararc graphs where
all thie arcs are of unit length.
The final two kinds of circulararc graphs
studied here Eire A circulEireltc graphs and
9 circular-arc graphs. A circular-arc graphs
exist if every three mutually adjacent Etrcs in the
circulsir-arc represent sit ion have a non-empty
intersection. 0 circular-Etrc graphs exist if the
arcs corresponding to every msocimal clique have a
non-empty intersection; they also happen to be
subsets of A circularEire graphs.
VEirious algorithms eire presented which
help one to recognize certain kinds of circular-
arc graphs and also to construct them. Others Eire
alluded to but are not actually presented in this
paper.
CirculEir-arc graphs have had a relatively
recent origin and enjoy a number of applications;
some of these Eure found in genetics, time spans,
data analysis, and traffic control.


V
The form and content of this abstract Eire
approved- I recommend its publication.
Signed


DEDICATION
to my family,
Mary, Joshua, Caleb, and Abigail


ACKNOWLEDGEMENTS
I would like to thank Jennifer Ryan, the
chairperson of my thesis committee, for her
v-aluable insights and suggestions.
I would also like to thank Richard
Lundgren, a member of my thesis committee, for his
encouragement and excellent teaching in the area
of applied mathematics.
Bill Cherowitzo has been my advisor and
was also on my thesis committee; I appreciate the
time and advice he has given to me.
The math department at the University of
Colorado, Denver provided valuable clerical
assistance, and for that, I am grateful.
Barnes Business College, my employer,
constantly changed my schedule and provided other
considerations to enable me to finish my thesis
and degree.
I appreciate my parents for instilling in
me early a desire to learn, my extended family for
their support, and especially, my wife, Mary, and
my children, Joshua, Caleb, and Abigail for being
so patient and tolerant-
Finally, I would like to thank the Lord
who has helped me in many ways-


CONTENTS
CHAPTER
I. INTRODUCTION ........................... 1
Definition .......................... 2
Examples ............................ 5
History.....................- . 8
II- CHARACTERIZATIONS OF CIRCULAR-ARC
GRAPHS.............................. 11
Definitions......................... 11
Characterizations and Algorithms . 16
III- INTERVAL CIRCULAR-ARC GRAPHS .......... 48
Definition .............----- 48
Unit Interval Graphs............... 52
Proper Interval Graphs ............. 54
Fulkerson-Gross Algorithm .......... 58
IV. PROPER CIRCULAR-ARC GRAPHS .......... 65
Definition.......................... 65
Theorems ............... 69
V. UNIT CIRCULAR-ARC GRAPHS.........- 78
Definition.......................... 78
Theorem............................. 83


ix
VI. A AND 9 CIRCULAR-ARC GRAPHS.............. 85
A Circular-arc graphs.................. 85
Theorem ............................. 90
0 Circulararc graphs.................. 92
Theorem.............................. 96
Recognition Algorithm ...... 96
VII. APPLICATIONS OF CIRCULAR-ARC
GRAPHS.................................103
Genetics...............................103
Time Spans.............................108
Data Analysis.................... . 113
VIII. TRAFFIC CONTROL APPLICATION ............ 120
IX. CONCLUSION . ...................... 132
BIBLIOGRAPHY
135



CHAPTER I
INTRODUCTION
A graph G = (V,E) consists of a finite set
of vertices V and a collection E of ordered pairs
called the edge set of G. Circular-arc graphs
belong to a class known as intersection graphs. If
3 is a family of nonempty sets, then the graph G,
the intersection graph of 7, can be defined as
follows: V(G) = 7 and if S,T E 7 with S 2 T, then
|S,T| E E(G) 4~ S fl T 2 0. For example, let
3^ = |A,B,C,D,E,F| and define A,B,C,D,E,F as
follows:
A = |l,2,3,4l
B = |l,3,6l
C = 17,8,91
D = |3,8,lll
E = |6,7,8,9,10l
F = |l,5l
Since A n B 0, fA,Bl E E(G). Analyzing the rest
of the sets produces the intersection graph of 7^:


2
E A
Another example of an intersection graph
with = |A,B,C,Dl and A,B,C,D defined as follows
is given below:
A = fl,2,3|
B = |3,4,5|
C = |1,2,51
D = |5l
Definition
Suppose that 3 is a family of arcs on a
circle- Let G be a graph such that a one-to-one
correspondence between vertex CK and arc exists
where (K and CK are joined by an edge if and only
if n Cj 2 0. In other words, two distinct
vertices are adjacent if and only if the
corresponding arcs overlap. If the arcs are all
open or closed (the choice is immaterial as long


3
as it is consistent), then G is called a circular-
arc graph.
The circular-arc representation of the
intersection graph of 3^ would be:
and the representation of the intersection graph
of Sg would be:
As is pictured, arcs overlap if and only
if their corresponding vertices share an edge.
However, not all intersection graphs have


circulararc representations. Let
= |A,B,C,D,E,F| such that:
A = |l,2l
B = |2,3|
C = f 5,6|
D = |6,7|
E = f 7,8|
F = |5,8I
An intersection graph for these sets would be:
A
C
F
B
D
E
However, a circulararc representation
would be impossible. If |C,Fl £ E(G), then it
would be:


5

However, since |C,F| E E(G), C needs to overlap F,
but that would cause C or F to overlap A and B or
D and E, and then new edges would have been
created. Therefore, all circulararc graphs are
intersection graphs, but the converse is not true.
Examples
Here are several examples of graphs
followed by their circulararc representations:


6
B


7


8
History
In 1957, G. Hajos \7~\ posed the following
problem:
Given a finite number of intervals on a
straight line, a graph associated with this
set of intervals can be constructed in the
following manner: each interval corresponds
to a vertex of the graph, and two vertices are
connected by an edge if and only if the
corresponding intervals overlap at least
partially. The question is whether a given
graph is isomorphic to one of the graphs just
characterized.
The real interest in interval graphs grew
out of their use by the Nobel laureate biologist,
Seymour Benzer, during his investigations of the
fine structure of the gene. Geneticists have
treated the chromosome as a linear arrangement of
genes, and Benzer wanted to find out if this was
true for the fine structure inside the gene.


This structure cannot be directly
observed, but mutations (which are changes in the
structure) can be studied- Benzer assumed that
9
mutations involve changes in connected
substructures of the gene and was able to surmise
whether or not two mutations overlapped- With the
overlap information, he then had to decide if the
mutations studied could be part of a linear
chain. Was the hypothesis (that the,structure in
the gene is linear) consistent with the overlap
inf ormat ion?
Stating the problem in graph theory terms,
let a graph G be defined as follows: the
substructures being studied are the vertices of G
and two distinct substructures have an edge
between them if and only if they are known to
overlap- Can vertices be mapped into intervals in
the real line so that two vertices intersect if
and only if the corresponding vertices are joined
by an edge? Is G an interval graph?
Benzer obtained the overlap data for a
small portion of the genetic structure of a
certain virus and it turned out that the matrix
defined an interval graph- Thus, he was able to


10
show that the data was consistent with the
hypothesis of linearity [1].
Within a few years after Benzerrs paper, a
number of characterizations and applications had
been found for interval graphs. However,
sometimes the data did not fit on a unidimensional
continuum without causing confusion (because
sometimes an intersection between extrema existed)
and so the natural mathematical generalization of
interval graphs, the circulararc graph, was
considered. By wrapping the two ends of an
interval graph around into a circle, the circular-
arc graph was produced, and a new area of study
and applications was opened up.


CHAPTER II
CHARACTERIZATIONS OF CIRCULAR-ARC GRAPHS
A number of characterizations have been
given for circulararc graphs. However, we need
to define the basic terms involved in these
characterizations and proofs before we proceed any
further.
Definitions
M(G) will be used to represent the (0,1)
adjacency matrix for a graph G where entry
(i, j) = 1 if vertices x^. and x^ are adjacent and
will be 0 otherwise. M(G) must be symmetric and
have 0's on the main diagonal. Let G be the
following graph:
Its adjacency matrix, M(G), would be:


12
0 10 0 1
10 111
0 10 11
0 110 1
11110
M (G) is defined to be the augmented
adjacency matrix for a graph G where
M (G) = M(G) + I with I the identity matrix;
*
therefore, M (G) is M(G) with l's on the main
diagonal. If G is the graph pictured above, then
M*(G) will be:
110 0 1
11111
0 1111
0 1111
11111
If the l's in each column of a (0,1)
matrix appear in a consecutive order (i.e., no 0rs
appear between any lrs in any column), then the
matrix has the consecutive l's property for
columns. The following matrix has the consecutive
lrs property for columns:
0 1 1 0 1
1110 1
110 0 1
10 0 11
0 0 0 1 1


13
On the other hand, the next matrix does not have
that property because the l's in the first column
are not consecutive:
1110 1
0 1111
0 1111
110 11
110 0 0
A (0*1) matrix has the circular l's
property for columns if the rows can be permuted
so that the l's appear in a circularly consecutive
fashion (as if the matrix was wrapped around a
cylinder). The following matrix has this
property:
1 10 1 1
10 10 1
0 0 10 0
0 110 0
110 10
However, the next matrix does not have this
property because the l's in the first and second
columns are not circularly consecutive, and the
rows cannot be permuted to obtain circular l's.


14
1110 1
0 0 10 0
10 0 10
0 10 10
10 10 1
Of course, a matrix with consecutive l's
automatically has circular l's.
Let M be a (0,1) matrix with l's on the
main diagonal. Let u^ be the circular set of l's
in column i starting at the main diagonal and
going down (and around) as far as possible (until
a 0 is encountered). Let v^ be the analogous set
of 1-entries in row i starting at the main
diagonal and going right (thus, entry (i,j) is in
v^ if and only if entry (j,i) is in u^). Then M
has quasicircular l's if the u^'s and v^'s
contain all the l's in M. The following matrix
has quasi-circular l's:
1 1 1 1 1 0
1 1 1 0 0 0
1 1 1 0 0 0
1 0 0 1 1 1
1 0 0 1 1 0
0 0 0 1 0 1
On the other hand, the next matrix does not have
quasi-circular l's because the (2,5) and (5,2)
entries are not contained in any u. or v.:
J 1 x


15
1 0 0 0 0
0 110 1
0 1110
0 0 111
0 10 11
A symmetric (0,1) matrix has circularly
compatible lrs if it has circular lrs and if some
cyclical permutation causes the last 1 in the
circular order in the second column to be at least
as low as the last 1 in the circular order in the
first column (ignoring columns with all 0rs and
l's). An example of such a matrix is:
1 1 1 1 0 0 1
1 1 1 1 0 0 0
1 1 1 1 1 0 0
1 1 1 1 1 1 1
0 0 1 1 1 1 1
0 0 0 1 1 1 1
1 0 0 1 1 1 1
The following matrix does not satisfy the
condition in its present form:
11110
1110 0
1110 0
10 0 1 1
0 0 0 1 1
However, if the fifth column is cyclicly permuted
to become the first (with the appropriate row


16
permutation), the following matrix results:
1 0 0 0 1
0 1111
0 1110
0 1110
_1 1 0 0 1_
This matrix does meet the conditions with its
present form and thus, does have circularly
compatible lrs.
Characterizations and Algorithms
The following theorem demonstrates a
method for recognizing circular-arc graphs and
constructing a circulararc representation.
However, since the characterization is quantified
over all permutations of the vertices, this method
will be impractical for all but very small graphs.
Theorem 8.1 [813: G is a circular-arc graph
if and only if its vertices can be indexed so
ac
that M (G) has quasicircular l's.
Proof: Let G be a 'circulararc graph and
assume (without loss of generality) that no arc
equals the entire circle, the arcs are open, and
no arcs share a common counterclockwise endpoint.
Choose an arbitrary point and move clockwise around


17
the circle, indexing the vertices by their
counterclockwise endpoint, v^ is adjacent to Vj
if and only if the counterclockwise endpoint of v.
J
(the.arc corresponding to vertex v.) lies within
J
v^ or vice versa. Either each of v^+^, . Vj
intersects v. or v..., . v. intersects v..
i J+1 i J
This is equivalent to saying that M (G) has quasi-
circular l's.
Conversely, index the vertices to satisfy
the conditions and then construct a circulararc
*
representation for G (assume that M (G) has quasi-
circular l's). Draw and label an nhour clock
where p^ is the kth hour marker, and n is the
number of vertices. If v is the first vertex in
m.
l
the sequence v^+^, v^+g, . v^ not adjacent
to v^, then draw an open arc clockwise from p^ to
p and call it v.. v. intersects v. if and only
HK 11 j
if either p. E v. or p. 6 v.. But if adj(v.) is
J i i j . i
the set of all vertices adjacent to v^, then
Pj E v -- vi+1, . Vj E Adj(vj) Therefore,
v^Vj E E (the edge set of G) if and only if
v. D v. 2 0.1
i J
If we let G be the following graph,


18
A B
then M £G) will be:
11110
11110
11110
11111
0 0 0 1 1
The lrs are all accounted for as in the definition
of quasi-circular l's, and so, according to the
theorem, G has a circular-arc representation:
If G is this graph


19
A
then M (G) will be:
1110 11
110 0 10
10 10 0 1
0 0 0 1 0 1
110 0 10
10 110 1
This matrix does not have quasi-circular lrs;
however, if rows 4 and 6 are permuted and rows 3
and 5 are permuted (with appropriate column
permut at ions),
produced.
matrix with quasi
1 1 1 1 1 0
1 1 1 0 0 0
1 1 1 0 0 0
1 0 0 1 1 1
1 0 0 1 1 0
0 0 0 1 0 1
circular l's is
This action effectively switched vertices D and F
and also switched vertices C and E on the graph-
Thus, it is a circular-arc graph with this
representation:


20
On the other hand, this graph G
B
E
C
D
A
has M (G) without quasicircular l's.
1 0 0 0 0
0 110 1
0 1110
0 0 111
0 10 11
No permutation has the desired property and so G
does not have a circulararc representation.
Conversely, if G is a graph like this one,


21
A
B
E
C.______________.D
with circular-arc representation

then M (G) should have quasi-circular lrs.
110 0 0
110 0 0
0 0 110
0 0 110
0 0 0 0 1
It is apparent that it does have this property.
Another way of stating this theorem is as


22
follows C5J:
An undirected graph G = (V,E) is a circular-
arc graph if and only if its vertices can be
circularly indexed v., v_, . v so that
12 n
for all i and j,
v
. v .
i J
G
either
or
Vj G AdjOp
v G Adj(vj)
(if i < j,
vj+, .
then v. ,
j+1
n
1'
, v. means
l
V-
The following graph illustrates this
alternate statement of the theorem:
2
We can see that these statements Eire all true:
V1V2 G E V2
V2V3 G E V3
V2V4 G E CO >
V3V4 G E V4
V3V5 G E V4
V4V5 G E lO !>
G AdjOp
G Adj(v2)
v4 G Adj(v2)
G Adj(v3)
v5 G Adj(v3)
^ Adj(v4)
Therefore, this must be a circular-arc graph and


23
its circulararc representation is pictured below:
Theorem 2.2 £17]: Let 11^ be a (0,1) matrix.
Form the matrix Mg from M^ by complementing
(interchanging 0's and lrs) those columns with
a 1 in the first row of M^ Then has the
circular lrs property for columns if and only
if Mg has the consecutive lrs property for
columns.
Proof: If a column has circular lrs with a
1 in the first row, it must have consecutive 0rs.
So complementing the column would result in
consecutive l's. If a column has circular l's
with a 0 in the first row, it must have consecutive
lrs and remains unchanged. Therefore, if has
circular l's, Mg must have consecutive lrs.
2
5
Conversely, Mg has consecutive l's with
the first row 0 which means it must have circular


24
Ors. Complementing columns with circular 0rs
produces circular lrs. Thus, if Mg has
consecutive lrs, must have circular
Suppose M^ has circular 1 r s :
1 0 1 1 0
1 0 0 1 1
0 1 0 1 1
0 1 1 0 1
1 1 1 0 0
Then Mg obviously has consecutive l's:
0 0 0 0 0
0 0 10 1
1110 1
110 11
0 10 10
Theorem 3.3 £31]: 6 is a circular-arc graph
*
if M (G) has the consecutive 0rs property for
columns.
Proof: Index the vertices of G so that
the consecutive 0rs property for columns appears.
is the set of columns whose 0rs are below the
main diagonal and Cg is the set whose 0s are above
the main diagonal with R^' and Rg being the
corresponding row sets. If columns i and j are in
with i < j, then all the lrs in j are above the


25
main diagonal and entry (i,j) = 1 so forms a
clique; similarly, Cg forms a clique. Draw arcs
of the same size representing Rg in successive
order with a common intersection but separate
endpoints. Now draw an arc representing each
column in which is the complement of the arcs
representing the rows which contain 0's in that
column. Any'vertex not in or Cg will have all
lrs and the arc should intersect all others.
Thus, a circulararc representation has been
created and therefore exists.!
If G is the following graph,
A
then M (G) is
1 1 0 0 1 1
1 1 0 0 0 1
0 0 1 1 1 1
0 0 1 1 1 1
1 0 1 1 1 1
1 1 1 1 1 1


26
= |A,B| and Cg = |C,D,E|. Therefore, the
following circular-arc representation could be
constructed using the algorithm.
Another example involves the graph
A
Since M (G) would be
1 1 1 1 0 0 1
1 1 1 1 0 0 0
1 1 1 1 1 0 0
1 1 1 1 1 1 1
0 0 1 1 1 1 1
0 0 0 1 1 1 1
1 0 0 1 1 1 1


27
= |A,B,C| and = |E,F,G|. Using the
algorithm, we would construct this circular-arc
representation:
However, the converse of Theorem 2-3 is
not true- If G was
A
then M (G) would be
11111
110 0 0
10 10 0
10 0 10
1 0 0 0 1
No permutation will produce consecutive 0rs. Yet
G has the following circulararc representation:


28

Theorem 2.4 [21]: An undirected graph 6 is a
circular-arc graph if its augmented adjacency
matrix has the circular l's property for
columns.
*
Proof: If M (G) has the circular lrs
property, and the vertices of G are indexed so
*
that M (G) has quasi-circular l's, then G is a
circularsire graph according to Theorem 2.1. If
that is not true, let the (j,k) entry be a 1 not
contained in u^ or v^ (of the quasi-circular
sets). We can assume this entry is in the last
row (by a cyclic permutation, if necessary) and
that (l,k) is in v^. The (l,k) entry has to be a 1
(since the l's are circular), but the (j,k) entry
is not in u, Since the 0's in each row and column
k
are circular, the 0's in row j must be to the left
of the entry (j,k) and the 0's in row 1 must be to
the right of entry (l,k). Since no column has a 0


29
*
in both the first and last row, then M (G) has the
consecutive lrs property for columns and G is a
circular-arc graph according to Theorem 2.3.1
We can test for the circular l's property
by using the FulkersonGross algorithm (which
tests for consecutive l's and will be presented in
the next chapter) and Theorem 2.2. If an
appropriate arrangement exists, then a circular-
arc graph could be constructed using the algorithm
from Theorem 2.1 or Theorem 2.3.
Let G be the graph represented by:
A B
xc
Then M (G) would be:
1 1 0 0 0 1
1 1 1 0 0 0
0 1 1 1 0 0
0 0 1 1 1 0
0 0 0 1 1 1
1 0 0 0 1 1
*
Upon inspection, it can be seen that M (G) has
quasi-circular l's. Therefore, a circular-arc


30
representation exists and can be constructed using
the algorithm in Theorem 2.1.
F
If G is this graph,
A B
then M (G) is
1 1 1 0 0 0
1 1 1 0 0 1
1 1 1 1 0 1
0 0 1 1 1 1
0 0 0 1 1 1
0 1 1 1 1 1
which does not have quasicircular l's. However,
it does have consecutive 0rs. Therefore, we can


31
construct a circular-arc graph using the algorithm
of Theorem 2.3. = |A,B,C| and Cg = fD,E,F|.
The converse of Theorem 2.4 is false. The
following graph, G
6 1
has M (G)
1 1 1 0 0 1 1
1 1 1 1 0 0 1
1 1 1 0 0 0 0
0 1 0 1 1 1 1
0 0 0 1 1 1 0
1 0 0 1 1 1 1
1 1 0 1 0 1 1
which does not have the circular lrs property.


32
However, it does have quasicircular lrs and so a
circular-arc representation exists:
Theorem 2.5 [21]: Suppose the n vertices of G
are indexed so that the lrs in each column of
*
M (G) are circular [so by Theorem 2.4, G is a
circular-arc graph]. If this arrangement of
*
M (G) does not have circularly compatible lrs,
Xc
then II (G) has the consecutive 0rs property for
columns and the vertices partition into two
cliques.
Proof: If a row (or column) is all lrs,
then the matrix can be cyclicly permuted to make
that row first and thus, the O's will be
consecutive and the vertex corresponding to that
row can be added to either of the two cliques
demonstrated in the proof of Theorem 2.3. If no
*
row has all l's and the arrangement of M (G)


33
doesn't have circularly compatible l's,
i 1
1 1
1
j 111
0
1 i
0
i :
k 1 0 0 0 0
o o
i i i 11 i
l
l
l
l
l
then the rows are ordered so that the last l's in
the circular set of l's in the first and second
columns are (k,l) and (j,2) with j < k. If (k,2)
is not 0, then columns 1 and 2 have 0's in
different rows and can be cyclicly permuted (1, n,
n1, ... 2) to yield consecutive 0's. If (k,2)
is 0, then the 0's in row k occur between the
first column and the main diagonal. Let (i,n) be
the last 1 of the circular l's in the last
column. If i £ k, then cyclicly permute the last
column to become the first and continue until
i < k or i = n (if i £ k and i 2 n, then the last
1 in the circular set in the first column is at
least one entry lower (after a permutation), but
no column is all l's so eventually i < k or
i = n)- (k,n) is 1 since all 0's in k are to the


34
left of the main diagonal. The last column has
all l's from k down; no row has O's in both the
*
first and last column so M (G) has consecutive O's
with no columns all l's, and the proof of
Theorem 2.3 indicates that the vertices of G
partition into two cliques.!
If G represents the following graph,
A B
then its augmented adjacency matrix.would be
1 1 1 0 0 1 1
1 1 0 0 0 1 1
1 0 1 1 1 1 1
0 0 1 1 1 0 0
0 0 1 1 1 1 1
1 1 1 0 1 1 1
i 1 1 0 1 1 1
This matrix has circular l's but does not have
circularly compatible l's. Therefore, following
the proof of Theorem 2.5, we can cyclicly permute
this matrix twice and obtain this matrix:


35
111110 1
111110 1
111110 0
11110 0 0
1 1 1 0 1 1 1
0 0 0 0 1 1 1
110 0 111
This matrix does exhibit the consecutive O's
property and can be partitioned into the cliques
= |A,B,F,G| and Cg = fE,C,D|. In this case,
i < k after the two permutations. Its circular-
arc representation is pictured below:
A second graph illustrates the situation
where i fC k, but i = n eventually.
F


36
A B
F E
Its augmented adjacency matrix is:
1 1 1 1 0 0 0 1
1 1 0 0 0 1 1 1
1 0 1 1 1 1 1 1
1 0 1 1 i 1 i 1
0 0 1 1 i 1 1 1
0 1 1 1 1 1 1 0
0 1 1 i 1 1 1 0
1 1 1 1 1 0 0 1
This does not have circularly compatible lrs, but
it does have circular l's. Therefore, if we
permute this matrix once, we'll obtain this
matrix:
1 1 1 i 1 1 0 0
1 1 1 1 i 0 0 0
1 1 1 0 0 0 1 1
1 1 0 1 1 1 1 1
1 1 0 1 1 1 1 1
1 0 0 1 1 1 1 1
0 0 1 1 1 1 1 1
0 0 1 1 : 1 1 1 1
Since i = n, this matrix does have consecutive 0rs
and can be partitioned into the two cliques,


37
C1 = fA,B,H| and = |C,D,E,F,G|. Its circular-
arc representation can be seen below:
B
Coloring problems have a number of
applications in graph theory and basically answer
the question of how many different colors it takes
to color the vertices of a graph if adjacent
vertices do not share the same color. Similarly,
we can color the arcs of a circularEire
representation so that no two overlapping arcs
have the same color. In the following theorem,
Y (F) is the chromatic number (number of colors
required) of a family F of arcs, rSUp(F) is the
largest size of an overlap set in F, and r^nj.(F)
is the smallest size of an overlap set in F where
we assume that r (F) > r. (F). It actually
provides the best possible bound for the chromatic
number.


38
Theorem 2.6 [19]: For a family of arcs,
V(P) < rsup(P) + rinfCF) s SrsupCP) 1.
Proof: If S is an overlap set where
|S| = rinf(F) then Y(S) = |S|. Break F in S and
treat F S as a family of intervals. Then
Y(F S) = r (F S) = r (F). So
v 7 supv 7 supv 7
Y(F) £ r (F) + r. -(F). Since r (F) > r. -(F),
v ^ supN 7 infv 7 supv 7 infv 7
r (F) 1 > r. -(F) so
supv 7 ~ inf' 7
r (F)+r. -(F)^r (F)+r (F)-l=2r (F)-l.I
supx x inf sup sup supN 7
Suppose we use this graph:
F A
The family of arcs F would be the circular-arc
representation for this graph and is pictured
below:


39
G
r (F) = 3 and r. (F) = 2 so
supv y infv 7
Y(F) £3 + 2^2* 31=5- This bound isn't
very good sometimes; in fact, Y(F) = 3 in this
case since the following vertices could be colored
the same: |B,F|, |A,D|, |C,E,Gl-
Another example would involve this graph:
C F
Its circulararc representation is:


40
r (F) = 5 and r. -(F) = 2 so
supv ' inf v
Y(F) £ 5 + 2 = 7 £ 2 5 1 = 9- In fact, a
coloring of F shows that Y(F) = 5 since the
following vertices can be colored the same:
fA,F|, fC,D|, |B,E1, |G|, |H|.
If we added (B,F) to the graph, it would
still be a circulararc graph and would not change
the chromatic number, but it would give us a
closer bound. This is because as Tucker proved in
[19], if G is a circular-arc graph and G and Gr
have no odd holes, then G is perfect. Since the
last example would have no odd holes (nor would
its complement) if (B,F) was added, it must be
perfect which means that the size of the largest
clique is the same as the chromatic number Y.
Since the largest clique is DEFGH, o(G) = 5 which
implies Y(G) = 5, as we have already discovered.


41
Before presenting the next theorem, we must
define some terms. For a graph G(V) and a family
A^, . . ., of subsets of V, we will denote by
li(A^,. . . AjP the k x n matrix whose entry
is 1 if v. E A. and 0 if v. 0 A.. Two arcs
Eire considered overlapping if they intersect and
neither is contained in the other. If the set
S = 5s., . ., s | is a subset of all the arcs on
* 1 r5
the circle with s^, 1 < i £ r satisfying
i) s^ does not contain endpoints of the arcs
ii) s^ is an Eire or is the intersection of
two overlapping su:cs or one piece of a
disjoint intersection
then S is the set of primitive arcs. For every
1 £ i £ r, Vi = fv | v E V, si C v|.
Theorem 2.7 [4]: Let G(V) be a circular-arc
graph and F its representing family of arcs.
Then [1(7^, . ., V ) has the circular l's
property.
Proof: Assume that s^, . ., sr appeEir
in a circular consecutive order. Every arc Vj
contains a circulEir consecutive sequence of primi-
tive arcs. But s. C v. if and only if v. C V..
i J ' J ~ i
So the l's in column j appear in a circulEtr


42
consecutive order. Therefore, ... Vr)
has a circular l's form.!
Consider the following graph:
A B
E
D C
If this is the representing family of arcs,
then the set of Vrs would be:
V = |D,E|
V2 = ^BE^
V3 = |A,B,C
v4 = |C,D|
The resulting matrix then has the circular l's


property as can be seen below:
0 0 0 1 1
0 10 0 1
1110 0
0 0 110
Another example would involve this graph
A B
Its family of representing arcs would be:
D
The V's would then be:


44
V = |A,B,G|
V2 = IB,C,D1
V3 = fC,D,E,F|
V4 = fA,E,F,G|
which results in the following matrix with the
circular l's property:
1 1 0 0 0 0 1
0 1 1 1 0 0 0
0 0 1 1 1 1 0
1 0 0 0 1 1 1
A family A^, . ., A^ of completely
connected sets of vertices (i.e. cliques) of a
graph G(V) is called a covering system for G if it
k
satisfies: V = U A.; if i 2 j, then A. £ A.; and
i=l 1 l j
for every two adjacent vertices u,v, there exists
a set A^ containing them.
Theorem 2.8 A graph G(V) is a circular-
arc graph if and only if it has a covering
system A^, . ., A^. such that
. ., Ak) has the circular l's
property.
Proof: If G(V) is a circulararc graph, F
is the family of representing arcs, S is the set


45
of primitive arcs, and V\ = fv | v E V, s^ C v|,
then V^, . ., must be a covering system.
Since every arc contains a primitive arc,
V., . ., V, would contain all of the vertices.
1* k
Also, if V. C V., then s. = s. and V. = V.
i J i J i j
implying that i = j- So V. ^ V.. Since
J
V^, . ., is a covering system,
. ., VjP has the circular l's property by
Theorem 2-7.
Conversely, if A^, . ., A^ is a covering
system for G so that ^(A^, . ., A^.) has the
circular l's property, then mark points 1, . -, k
consecutively clockwise on a circle. Let the lrs
in column i appear in circularly consecutive order
with the first 1 in row m and the last one in row
p. If m = 1, then v^ = (k,p); otherwise,
v^ = (m l,p). If column i contains all l's,
then v. = (k,k). Two vertices v.v. can be
i x j
adjacent only if v.v. 6 A where 1 £ s £ k.
1 J s
Therefore, (s l,s) C v^ D v^ (if s = 1, then
let s = k) and this is the circular-arc
representation of G-I
Consider the following graph:


46
A covering system for this graph would be:
A = f1,4,6,71 A5 = |2,3,5,8|
Ag = |1,5,6,7I Ag = |3,5,6,8|
A3 = f1,2,5,71 A7 = |3,4,6,8l
A4 = |2,5,7,8I Ag = |4,6,7,8l
Therefore, ji(A^, . Ag) in circular lrs form
is:
1 0 0 1 0 1 1 0
1 0 0 0 1 1 1 0
1 1 0 0 1 0 i 0
0 1 0 0 1 0 1 1
0 1 1 0 1 0 0 1
0 0 1 0 1 1 0 1
0 0 1 1 0 1 0 1
0 0 0 1 0 1 1 1
and the circulararc representation is:


47
1
These selected characterizations of
circular-arc graphs seem to be the basic ones
discovered so far; however, many other (perhaps)
less important characterizations can be found in
the literature, said they are also as interesting
and intriguing-
Algorithms for finding a maximum
independent set [4], a minimum covering by cliques
of a circulararc graph £4], a maximum clique of a
circulararc graph [4], and an efficient test for
whether an nvertex graph is a circulararc graph
along with its construction [20] are also
presented in the literature; however, they will be
omitted here since their proofs and efficient
implementation are quite involved, and an
exhaustive presentation of circular-arc graphs
isn't possible.


CHAPTER III
INTERVAL CIRCULAR-ARC GRAPHS
Interval graphs are probably the most
well-known circularsore graphs, having been
defined earlier than circular-arc graphs and
enjoying a variety of applications, some of which
will be discussed later. In fact, an entire thesis
could be written solely on interval graphs so our
coverage here will be somewhat superficial.
Definition
A graph G = (V,E) is an interval graph if
and only if there is an assignment J of a real
interval J(u) to each u G V so that for all
u 2 v e v,
fu,v| G E -- J(u) D J(v) £ 0.
In other words, G is an interval graph if it is
the intersection graph of a family of closed (or
open) intervals on a line where the intervals
overlap if the vertices intersect [11].
Suppose 3(A,...,G) is an intersection


49
graph such that
A
B
C
D
E
F
G
11 4,5|
f1,2,5|
|l,2,3l
|2,3,6l
|3,6,7|
|3,7,8|
|3,8,9|
Then the graph of 3 is pictured below:
C
3 is also an interval graph since it can be
represented as a family of intervals on a line:
E
F
G
Another example of an interval graph is


50
F E
with its interval representation:
A--------- C------------------
B-----------------------
D-------------- F-------- E--------------
G------------------
H-------------------
Since the number line could be wrapped
around into a circle, it stands to reason that all
interval graphs sire also circulararc graphs.
Thus, the circular-arc representation of the first
interval graph pictured is
B
and the second one would be


51
Of course, if G is an interval graph, its
circulararc representation will never be a
complete circle (i.e., there will always be a gap
in the circle). This is because the two ends of
an interval never intersect, and so, if the
interval is wrapped around into a circle, there
must, of necessity, be a gap.
This leads to the conclusion that all
interval graphs are circulararc graphs but the
converse is not true, which can be shown by a
simple example. Suppose G is the following graph:
A
D
B
C
A circular-arc representation can be found easily
and is;


52

B
However, G could not be an interval
graph. We could get as far as
B------------
but now D must be drawn so it overlaps A and C but
not B. This is an impossibility since we cannot
wrap the line around. Therefore, this confirms
that circulararc graphs are not necessarily
interval graphs.
Unit Interval Graphs
A unit interval graph is the intersection
graph of a family of real intervals of unit
length. An example of a unit interval graph is:


53
A B
with its interval representation
A
B
C
D
E
F
G
and its circular-arc graph:
However, not all interval graphs are also
unit interval graphs. Consider the following
graph:


54
C
D
Its interval representation could be given as
follows:
A C
A, C, and F do not intersect at all; therefore, if
E is to span the gap to intersect A, C, and F
(which is required by the graph), it must be
longer them unit length. Therefore, this graph
cannot be a unit interval graph.
Proper Interval Graphs
A proper interval graph is another
subclass of interval graphs and is the intersection1
graph of a family of real intervals such that no
interval properly contains another (although two
may be identical). An example of one is:
/


55

with its interval representation:
A
B
C
D
E
F
and its circular-arc representation:

However, not all interval graphs are
proper interval graphs. The following simple
graph


56
is an interval graph as can be seen below:
A------------------------------
C ---------------- -------- -------------------- D
F ---- B ----- E
B intersects A but not C, D, E, or F so it
must be between C and D stnd hence is contained in
A. Therefore, this is not a proper interval
graph.
Interestingly enough, unit interval graphs
and proper interval graphs coincide. Thus, the
same examples could have been used for both.
Since no unit interval cam properly contain
smother unit interval, the graph must be proper.
To demonstrate that proper interval graphs must
also be unit interval graphs is more complicated;
however, Golumbic does this nicely [5]-
The vertex-maiximal clique incidence matrix
M(G) of a graph G is the incidence matrix of the
collection of msiximal cliques of G over the set of
vertices with the rows corresponding to the
cliques and the columns to the vertices. Using


57
this, we can demonstrate an important theorem for
interval graphs-
Theorem 3.1 [3]: A graph 6 is an interval
graph if and only if its vertex-maximal clique
incidence matrix M(G) can be permuted in such
a way as to have the consecutive lrs property
for columns.
Proof: Let M(G) have consecutive lrs. If
the first and last l's in the ith column of M(G)
appear in positions f^ and 1^, then G is the
intersection graph of the intervals
[f. 1, 1], i = 1,2,...,n.
Conversely, let G be the intersection
graph of intervals I., j = 1,---,n. If
J
e., e0, ... e are the distinct endpoints of those
l <3 m
intervals ordered such that e, < e < ... < e ,
12 m
then the m x n incidence matrix A = (a. .)
% ij-'*
obtained by setting a^. 0 or 1 according as
e^ G L has consecutive l's. Since M(G) is
obtained from A by deleting exterior rows, M(G)
has the consecutive l's property.!
Therefore, if the vertexmaximal clique
incidence matrix can be shown to have consecutive
l's, the graph is an interval graph. A nice
algorithm (called the Fulkerson-Gross algorithm)
exists to do just that Q3].


58
Fulkerson-Gross Algorithm
Two columns of M(G) are said to overlap if
they share the same clique, but neither is
contained in the other.' Find the column overlap
graph of M(G), and then find a corresponding non-
trivial spanning subtree of the overlap graph.
Three columns are said to be a rigid triple if the
first overlaps the second and the second overlaps
the third.
Begin with a rigid triple and position the
lrs so they sire consecutive, and yet the inner
products agree with the corresponding ones of
M(G). Because they are rigid, their position
relative to the other two columns is fixed. Add
another column which forms a rigid triple with two
previously used columns, and position the lrs
again so they are consecutive and yet have an inner
product which agrees with the corresponding ones
of M(G). Continue to do so until all the columns
have been used.
If forcing consecutive lrs at some point
produces an inner product which does not agree
with the corresponding ones of M(G), then the


59
process breaks down and M(G) does not have
consecutive l's.
Suppose G is the following graph:
A B
By inspection, the maximal cliques can be found to
be ACDE, BEG, ACEH, ABDE, and ACFH which produce
this matrix:
1 0 1 1 1 0 0 0
0 1 0 0 1 0 1 0
1 0 1 0 1 0 0 1
1 1 0 1 1 0 0 0
1 0 1 0 0 1 0 1
Obviously, this matrix does not exhibit
consecutive lrs in its present form. An overlap
graph for the matrix would be:


60

A B
and a spanning subtree of the connected components
would be:
Thus, if we start with A and work from the
spanning subgraph, we produce the following
configuration:
A B D
1
111
1 1
1
1
We continue to add columns, paying attention to
rigid triples, until we obtain this result:


61
A B D C E H G F
1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
Reordering the columns in alphabetical order and
filling in O's, we obtain a matrix with
consecut ive 1's:
0 1 0 0 1 0 1 0
1 1 0 1 1 0 0 0
0 0 1 1 1 0 0 0
1 0 1 0 1 0 0 1
1 0 1 0 0 1 0 1
Therefore, G is an interval graph and its interval
representation can be seen:
A
B
C
D
E
F
G
H
Its circulararc representation would be:


62
Another example would be this graph:
A B
The maximal cliques are DEFH, ABCD, EFG, and BCDH
which produce this matrix:
0 0 0 1 1 1 0 1
1 1 1 1 0 0 0 0
0 0 0 0 1 1 1 0
0 1 1 1 0 0 0 1
The overlap graph would be:


63
A B
Therefore, a spanning subtree of the connected
components is:
BAG
Applying the algorithm, we obtain:
H B C E D F A G
. 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
which translates to this matrix after filling in
the 0's and rearranging into alphabetical order:
0 0 0 0 1 1 1 0
0 0 0 1 1 1 0 1
o . 1 1 1 0 0 0 1
1 1 1 1 0 0 0 0


64
Since it has the consecutive l's property, it has
an interval representation:
A
B
C
D
E
F
G
H
with circular-arc graph:

There are many more things that could be
said about interval graphs, but, as was stated
earlier, that would produce a thesis in itself.
Therefore, we will refrain from doing so.


CHAPTER IV
PROPER CIRCULAR-ARC GRAPHS
Proper circulararc graphs form another
subset of circulararc graphs- These are
analogous to proper interval graphs.
Definition
Proper circular-arc graphs are, of course,
circulararc graphs- If, in addition, a
representation exists where no arc properly
contains another arc, then the graph is a proper
circulararc graph- A simple illustration of one
is given by this graph:
A
D
B
C
Its circular-arc representation is given as:


66
and it is obvious that no arc is properly
contained in another. Thus, this must be a proper
circular-arc graph.
Another example is given below:
Its circular-arc representation could be:


67
which doesn't appear to be proper since A is
* properly contained in B. However, a slight
alteration produces this representation:
Now no arc is properly contained in any other
arc. Since the definition only requires that some
representation exists, this is definitely a proper
circular-arc graph.
An example of a graph G which is not
proper is:


68
A
D
Its circular-arc representation would be:
Since B must overlap A and C, D would also have to
overlap either A or C if it extended past B.
Since AD, CD 0 E(G), D must be properly contained
within B and so this is not a proper circulararc
graph-
A more elaborate example which is not
proper is:
F A


69
Its circulararc representation would be:
E must be properly contained in D since D must
intersect with both G and B and E cannot intersect
either of them- Thus, this cannot be a proper
circular-arc graph.
There Eire several theorems about proper
circular-arc graphs. Tucker [.22] presents many,
but we will look at just three.
Theorems
Theorem 4.1 [SI]: G is a proper circulararc
graph if and Only if there is an arrangement
ate
of 11 (G) with circularly compatible lrs .
Proof: Assume G has a circulararc
representation. Start with any arc and number the
arcs of G by their counterclockwise endpoint as
ate
you proceed clockwise around the circle. If M (G)


70
doesn't have circular lrs, then v^ fl v^ 0 but
Vj fl vk = 0 with i < j < k. This would imply that
G wasn't proper since Vj C v^. Since G must be
*
proper, then M (G) must have circular l's. If,
however, the l's are not circularly compatible,
then that means some permutation produced the last
1 in column 1 below the last 1 in column 2- If
the last 1 in column 1 occurs in position k, then
v^ D v^ 2 0, Vg fl v^ = 0, and 1 < 2 < k so
Vg C v^. This could only happen if G was not
*c
proper. Since G is proper, M (G) must have
circularly compatible l's.
*
Conversely, if M (G) has circularly
compatible l's, then it certainly has circular
l's. According to the proof of Theorem 2.4, it
must then have quasi-circular l's or consecutive
0's. If it has quasi-circular l's, then use the
algorithm explained in Theorem 2.1 to draw a
circular-arc graph. If it has consecutive 0's,
then use the algorithm explained in Theorem 2.3 to
draw the circulararc graph. The only way that .
the circulararc graph won't be proper is if the
arcs have a common endpoint. In such cases,
either slightly shorten the longer arc or extend
the shorter one.I


71
Here is an example of a graph:
7 1
Its augmented adjacency matrix is given below:
1 1 1 1 0 0 1
1 1 1 1 0 0 0
1 1 1 1 1 0 0
1 1 1 1 1 1 1
0 0 1 1 1 1 1
0 0 0 1 1 1 1
1 0 0 1 1 1 1
This matrix has circularly compatible l's. It
also has quasi-circular l's and consecutive 0's;
therefore, if we use the algorithm explained in
Theorem 2.3, then = fl,2,3| and = |5,6,7f.
The following circular-arc representation is the
result:


72
Conversely, consider the following proper
circulararc graph representation:
F E
Its intersection graph would be:


F
E
It would then have an augmented adjacency matrix:
1 1 1 1
1 1 1 1
1 1 1 0
1 1 0 1
0 0 0 1
0 0 0 1
0 0 1 0
0 0 1 0
0 0 0 0
0 0 0 0
0 0 1 1
1 1 0 0
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
According to the theorem, this matrix
should have circular l's and circularly compatible
l's. If we permute rows 1 and 3 (which
effectively switches vertices A and C) with the
corresponding column permutation, we obtain:
1 1 1 0 0 0 1 1
1 1 1 1 0 0 0 0
1 1 1 1 0 0 0 0
0 1 1 1 1 1 0 0
0 0 0 1 1 1 1 1
0 0 0 1 1 1 1 1
1 0 0 0 1 1 1 1
1 0 0 0 1 1 1 1
It is easy to see that it has circular l's and


74
upon cyclicly permuting the rows and columns (1,
n, n-1, ..., 2), the circularly compatible l's
property is also demonstrated- Thus, this
illustrates Theorem 4-1.
Theorem 4.2 [5]: If 6 is a proper circular-
arc graph, then 6 has a proper circulararc
representation in which no two arcs share a
common endpoint and no two arcs together cover
the entire circle (i.e., they do not intersect
at both ends]).
Proof: Let A = fAxixey be a proper
circular-arc representation of G = (V,E). We may
assume that no two arcs share a common endpoint
since we could always slightly lengthen or shorten
one- Suppose and cover the entire circle so
that they intersect in two disjoint subarcs- Let
ct be the sequence of endpoints of the arcs going
clockwise from the counterclockwise endpoint of
A&- If a denotes the counterclockwise endpoint of
arc A& and a denotes its clockwise endpoint, then
[]a,b,b,a]] would be the subsequence of a involving
these letters and concatenation ct = tp, where t = Qa,...,b] and
p = [. -, b,.- -,a,- --]- For any x E V, [x,x]
could not appear in r since this would imply that
A C A which contradicts the claim that A is
x a
proper-


75
If ar = T'p, where Tr is obtained from t
by listing entries of t with hats followed by
those without hats but preserving the relative
order of each type, then for any x,y G V, the
subsequence of cr involving |x,x,y,y| will be
unchanged unless Qx,y] or £y,x] is a subsequence
of r. Assume [x,y] is in r (since the cases Eire
analogous). We allow that x may equal a or that y
may equal b. Since A is proper, x and y must
occur where indicated:
Ca, ..., x, ..., y, ..., b, ..., b, ..., a, ]
x I I------y-------1 lx --*
Either Cx,x,y,y] or Cx,y,y,x] is a subsequence of
x y
ends. Note that in the first case, x G r while in
the second, x £ t. After the transformation from
<7 to c', they become [x,y,x,y] or Cyxyx] which
correspond' to sires which overlap at only one end.
Let A' be a set of arcs corresponding to
a". Then Ar is a proper circular-arc
representation of G with fewer circle covering
pairs, and the theorem is proved by induction.!


76

Theorem 4.3 £5]* Every proper circular-arc
graph is also the graph of intersecting chords
of a circle.
Proof: First we will assume that no two
arcs cover the entire circle (Theorem 4.2). Draw
the chord connecting the endpoints of each arc on
the circle. It can be seen that arcs intersect if
and only if their chords intersect. The only way
that the chords would not intersect would be if
one arc was properly contained within the other,
but that would violate the stated conditions.!
If this graph is considered,
A
B
its circularEire representation would be:
A
D


77
It can be seen that chords do intersect only if
the arcs intersect.
Tucker gives many more structure theorems
for proper circulararc graphs in \22\ which are
varied and interesting.


CHAPTER V
UNIT CIRCULAR-ARC GRAPHS
Another sub-class of circular-arc graphs
is the unit circular-arc graph- It is analogous
to the unit interval graph.
there exists a circular-arc representation for G in
which every arc is of unit length. The length
would depend on the diameter of the circle, and
the arcs sire assumed to be either all open or all
closed.
Definition
A graph G is a unit circulararc graph if
An example of a unit circulararc graph
is:
A
E
D
with circular-arc representation:


Another example of a unit circular-arc
graph is:
with circulararc representation
Any unit interval graph must
of


80
necessity, be a unit circular-arc graph since the
interval graph can be wrapped around into a
circle, leaving a gap between the two ends. In
fact, the previous example is a unit interval
graph with this interval representation:
A ---------
B ---------
C ----------
D ----------
E ----------
However, if we add a vertex F to the graph
in this way:
B
F
D
it ceases to be a unit circulararc graph. It is
still a circulararc graph as this diagram shows:


81

but there is no way that F can be of unit length
and overlap with E but not overlap with A, B, C,
or D- Thus, it is not a unit circular-arc graph.
It is not proper either since F is properly
contained in E.
Unit interval graphs were seen earlier to
coincide with proper interval graphs. However,
unit circulararc graphs are a proper subset of
proper circulararc graphs. A unit circular-arc
graph must, of necessity, be a proper circulararc
graph since a unit arc cannot properly contain
another unit arc. If the endpoints do coincide,
one arc can simply be slipped slightly forward or
backward to eliminate this problem. Thus, all
these unit circulararc graphs are also proper
circularEire graphs.
However, it is possible for a circular-arc


graph to be proper but have no representation
where arcs have unit length. Consider this
example:
82
Its circular-arc representation would be:
As can be seen, this graph is proper since no arc
is properly contained in another. However, no
unit representation is possible. Assume there is
a unit representation where the arcs are closed.
Then A+C+E+G< 2nr (the circumference of the


83
circle) since they cannot intersect. However,
since B, D, F, and H must intersect at least at
their endpoints, then B+D+F+H^ 2nr.
Therefore, A < while B £ Unr so A < B which
means this cannot be a unit circular-arc graph-
In fact, if a proper circular-arc graph
has a subgraph like this:
it cannot be a circular-arc graph. The n-circuit
of the x.'s forces the circumference of the circle
1
to be at most n while containing an independent
set of y^'s that forces the circumference to
exceed n. Thus, any proper circular-arc graph
which contains a subgraph like this, called a CIn
subgraph, cannot be a unit circular-arc graph.
Theorem
Tucker generalizes the above idea in [22]
by letting C = (xQ, x^, ... xn1), be a circuit


84
of distinct vertices having corresponding arcs
Aq A^, . ., An_^ in a proper circular-arc model
with extending past the clockwise end of A^
If this arc sequence goes around the circle k
times, then C is called an (n,k)circuit.
Let I = (yQ, yt, ym_P be a
sequence of distinct vertices with corresponding
arcs Bq, B^, ... Bm_^ where B^+^ is the first
arc to follow B. but B. fl B. . = 0- If this
sequence goes around the circle X times, then I is
called an (m,X)independent set.
In a closed unit circulararc model of an
(n,k)-circuit, the circumference of the model can
be at most n/k. However, the circumference of an
(m,X)-independent set must exceed m/X. Thus, if
these occur in the same graph and m/X £ n/k, then
a unit circular-arc model cannot exist.
Tucker derives a theorem using a
combination of (n,k)circuits and 0X)independent
sets where he shows when a unit circulararc graph
is not a proper circular-arc graph fsee 22].
No matrix characterizations of unit
circulararc graphs exist. Thus, much work
remains to be done on unit circulararc graphs.


CHAPTER VI
A AND 0 CIRCULAR-ARC GRAPHS
Two more subclasses of circulararc graphs
are the A circulararc graph and the 0 circular-
arc graph. We will look at the A circulararc
graph first.
A Circulararc graphs
A graph is called a A circulararc graph
if it is the intersection graph of a family of
arcs on a circle, such that each three arcs, which
are mutually nondisjoint, have a non-empty
intersection []4]. An example of such a graph is:
with circular-arc representation:


86
2
The only three-arc combinations where
every pair intersects are:

125 127 146
167 235 238
346 348 356
468 478 567
147 156 157
257 258 278
358 368 467
568 578 678
Upon inspection, it can be seen that the
intersection of any three-arc combination is non-
empty which means it is a A circular-arc graph-
Another example of a A circulararc graph
is:


87
C F
with circulararc representation:
All the threearc combinations where each
pair of arcs intersect are:
ABC ABH ACH ADH BCH CFG
CFH CGH DEF DEG DEH DFG
DFH DGH EFG EFH EGH FGH
Upon inspection it is apparent that the
intersection of any threearc combination is non-
empty. Therefore, it must be a A circular-arc
graph.


88
An example of a graph which is not a
A circulararc graph is:
F A
with its circular-arc representation:
A fl F 2 0, A Cl G 0, and F n G 2 0, but
A n F n G = 0. There is no way to construct it to
rectify the situation; thus, this is not a
A circulararc graph.
Another example of a graph which is not a
A circulararc graph is:


89
F
D
E
Its circulararc representation is:

ABC is the only threearc combination, and yet the
intersection of the three is empty. To bring the
arcs around so that all three intersect would
force a new edge. For example, if B and C were
drawn to intersect A at some point, it would force
either B or C to intersect D.
Several definitions need to be covered
before we proceed further. Let Y(v) denote the
set of vertices adjacent to a vertex v. Then G^
will denote the subgraph generated by
Y(v.) U |v.|. Let cj", . ., C.* be all the
1
cliques of G^. Then define D^, . ., D^. to be


90
all the maximal elements of U |C*, . ., C* |.
i=l 1
Then ji(D^, . ., D^) will be the (0,1) incidence
matrix representing the maximal cliques
Theorem
Theorem 6.1 Q4]: G is a A circular-arc graph
if |i(D^, . ., Dk) has the circular lrs
property.
Proof: Consider a graph G such that
|jl(D^, . ., D^) has the circular l's property.
D^, . ., must be a covering system of G and
so we can construct a family of arcs as in the
proof of Theorem 2.8. If v^, v^, are mutually
adiacent, then v., v. E G. and G, must have a
i j h h
clique containing the three vertices. There
exists an s, 1 < s < k so that v, v., v. E D .
h j s
Therefore, v. fl v. n v. D (s l,s) and G is a
h l j v '
A circulararc graph.!
Consider the example used earlier:


91

C F
The vertices of the G.rs are listed and
1
are then followed by their maximal cliques:
Gi = ABCDH ABCH ADH
Gs = ABCH ABCH
3 = ABCFGH ABCH CFG
G4 = ADEFGH DEFGH ADH
G5 = DEFGH DEFGH
G6 = CDEFGH DEFGH CFG
G7 = CDEFGH DEFGH CFG
G8 = ABCDEFGH DEFGH ABCH
The maximal cliques are D^ = ABCH, D2 = ADH,
Dg = CFG, sind = DEFGH which are a covering
system for the graph. Of course, if the
intersection of a maximal clique is non-empty,
then smaller cliques which are subgraphs of
maximal cliques would also have a non-empty
intersection. Thus, ii(D^,D2,Dg,D4) would be: