Excerpt

Contents

Declaration

Acknowledgements

Dedication

Abstract

List of Symbols and Abbreviations

1 Introduction

1.1 Background of the Study

1.2 Rationale of the Project

1.3 Overview of the Project

2 Literature Review

3 Preliminaries

3.1 Definitions

4 Products of Graphs as Rectangle-Visibility Graphs

4.1 Definitions of the types of Graph Products

4.2 Cartesian Product

4.3 Direct Product

4.4 Strong Product

5 Conclusion

References

## ACKNOWLEDGEMENTS

Firstly, I would like to express my sincere gratitude to the Almighty God for helping me throughout my studies. I acknowledge the support and cooperation of my parents and siblings, Priscilla Ocloo and Monaliza Ocloo.

I owe my special gratitude to Prof. Neil Turok (Founder of AIMS), Prof. Francis Allotey (President of AIMS Ghana), Prof. Emmanuel Essel (Academic Director of AIMS Ghana) and Beatrice Kwawu (English Language and Communication/Program Officer) and to all other staff and the AIMS community for granting me the privilege of studies. I also do appreciate MasterCard Foundation for their financial support throughout my studies at AIMS.

My supervisor, Prof. Nancy Ann Neudauer (Pacific University, United states) for the continuous support of my essay, patience, motivation, and immense knowledge. Her guidance helped me in all the time of research and writing of this essay. I could not have imagined having a better advisor and mentor for my essay study. I also thank Lord Kavi and to all tutors, for their insightful comments and encouragement.

I also owe my special thanks to all friends and colleagues in AIMS, particularly to Sunday Taiwo, Wisdom Attipoe and William Affum for their precious support and critics in my research and my stay at AIMS Ghana.

## DEDICATION

To my parents Mr. and Mrs. Ocloo, and to my dearest friend Collins Abeka.

## Abstract

Visibility representation of a graph is a way of assigning the vertices of a graph to objects in a plane and the edges of the graph representing the positioning of the objects in such a way that they see one another. In this work, we consider representations of products of some classes of graphs as rectangle-visibility graphs (RVGs), i.e, graphs whose vertices are rectangles in the plane and edges are horizontal or vertical visibility. We focus on three types of graph products namely: cartesian, direct and strong products. We also investigate representations of products of some classes of graphs such as path, cycle with path, star with path and complete graphs that are RVGs. Furthermore, we discuss why some complete graphs are not RVGs. The results obtained are established by constructive proofs and yield linear-time layout.

Keywords: Rectangle-visibility graph, cartesian product, direct product and strong product.

## List of Figures

1.1 The VLSI component

3.1 A simple graph and a non-simple graph

3.2 Examples of a complete graph and a complete bipartite graph

3.3 A plane drawing of*K*

3.4 A complete graph*K*4 and its bar-visibility representation.

3.5 A complete graph*K*4 and its rv-representation

3.6 A complete graph*K*4 with its noncollinear rv-representation

3.7 A graph*G*with its unit rectangle-visibility representation

4.1 Construction of*P*3*×**P*

4.2 A rv-representation of*P*3*×**P*

4.3 Construction of*P*4*×**P*4 and its rv-representation

4.4 A rv-representation of*Pm**×**Pn*

4.5 Construction of*C*3*×**C*3 and its rv-representation

4.6 Construction of*C*6*×**P*2 and its rv-representation

4.7 Construction of*C*5*×**P*3 and its rv-representation

4.8 A rv-representation of*Cm**×**Pn*

4.9 Construction of*S*8*×**P*2 and its rv-representation

4.10 Construction of*S*9*×**P*2 and its rv-representation

4.11 Construction of*K*4*×**K*2 and its rv-representation

4.12 Construction of*P*3□*P*3 with its rv-representation

4.13 Construction of*P*5□*P*3 with its rv-representation

4.14 Construction of*C*3□*C*3 and its rv-representation

4.15 Construction of*C*6□*P*2 and its rv-representation

4.16 Construction of*C*5□*P*2 and its rv-representation

4.17 Construction of*K*4□*K*2 and its rv-representation

4.18 Construction of*P*3 ⊠*P*2 with its rv-representation

4.19 Construction of*P*3 ⊠*P*3 with its rv-representation

4.20 Construction of*C*3 ⊠*P*2 and its rv-representation

4.21 Construction of*C*4 ⊠*P*2 and its rv-representation

4.22 Construction of*K*4 ⊠*K*2 and its rv-representation

## 1. Introduction

### 1.1 Background of the Study

The history of graph theory may specifically be traced to 1735 when the Swiss mathematician Leonhard Euler solved the Konigsberg bridge problem ^{1}. The Konigsberg bridge problem origi- nated in the city of Konigsberg. The city had seven bridges which connected two islands. People in the city always wondered whether there was any way to walk over all the seven bridges only once. In 1736, Euler came out with a solution in terms of representing a set of vertices connected by edges (graph), and hence making the problem much easier to solve. This led to the applica- tion of graph theory in studies such as chemistry, electrical engineering, transportation network and many others. Another application of graph theory is found in the study of rectangle-visibility graphs. This representation of graphs have been extensively analysed over the past years, because of its application in the design of VLSI (Very-Large-Scale Integration) chip.

Visibility representation of a graph is by assigning the vertices of a graph to objects in a plane and the objects are placed in such a way that they can see each other. The visibility between these objects correspond to the edges of the graph. There have been many visibility representation studies on how to represent graphs. However, the most common ones are the bar-visibility graphs (BVGs) and rectangle-visibility graphs (RVGs). Bar-visibility graphs (BVGs) are those planar graphs whose vertices can be represented by horizontal line segments with adjacency determined by vertical visibility ^{2}.

On the other hand, rectangle-visibility graphs (RVGs) are graphs whose vertices are represented as rectangles in a plane and edges as horizontal or vertical visibility. An RVG is known to be the union of two planar graphs when the vertical and horizontal visibilities in its layouts are considered, and thus deconstructed into a union of two bar-visibility graphs^{3}. Hence, we say such graphs have thickness at most two. Shermer^{4}showed that it is NP-complete (nondeterministic polynomial time) to determine if a graph is an RVG, and so it is of interest to determine classes of graphs that are and those that are not RVGs.

The focus of this essay is to investigate representations of products of some classes of graphs as rectangle-visibility graphs.

### 1.2 Rationale of the Project

In making of computer chips, the Very-Large-Scale Integration is usually used, following a method of setting out and fixing transistors on the surface of a small chip in addition to the wired network between components ^{5}. Thus in designing chips, visibilities are considered between various electrical parts. Meanwhile visibility graphs are limited in their application to VLSI design as a result of the restriction of edges in the graph corresponding only to objects that see one another. However, they form a beginning point for the consideration of representing a physical circuit network as a graph ^{5}.

For such constructions, gates or other chip components represent horizontal bars or rectangles in the plane, and edges correspond to vertical visibilities between bars, or by horizontal and vertical visibilities between rectangles^{6}. These horizontal and vertical visibilities in RVGs form a typical example for two-layer chips with wires running vertically on one layer and horizontally on the other layer^{6}. Figure 1.1 is an example of the VLSI component.

illustration not visible in this excerpt

Figure 1.1: The VLSI component.

### 1.3 Overview of the Project

The organization of this essay is as follows. In Chapter 2, we provide a literature review on visibility representations, specifically rectangle-visibility representation. In Chapter 3, we present basic definitions and notations from graph theory and rectangle-visibility graphs. In Chapter 4, we study three types of graph products and investigate representations of products of some classes of graphs as rectangle-visibility graphs, and present our result. We also discuss why some complete graphs are not RVGs. Finally in Chapter 5, we give a conclusion of this work and state a possible extension of the results for future work.

## 2. Literature Review

In 1976, the first study of rectilinear objects in a two-dimensional plane with vertical and horizontal visibility was done by Garey et al. ^{7}. They recommended a strategy for testing printed circuit boards for the presence of possible (undesired) short circuits changes for the test minimization problem, into one of finding minimum vertex colourings of certain special graphs, called line-of- sight graphs. Also, they considered certain assumptions on the possible types of short circuits and analysed the structure of such graphs and showed that a well known and efficient algorithm can be used to colour them with a small number of colours.

Tamassia and Tollis^{8}studied visibility representations of planar graphs. They considered three types of visibility representations, and gave complete characterizations of classes of graphs that admit them. Tamassia and Tollis showed that a bar-visibility graph is a planar graph but not all planar graphs are bar-visibility graphs. Furthermore, they presented linear time algorithms for testing the existence and constructing visibility representations of planar graphs.

The study of rectangle-visibility graphs (RVGs) just like bar-visibility graphs was inspired by studies in ^{7}. Bose et al. ^{9} considered classes of graphs that are RVGs. They established that for 1 *≤** k **≤* 4, k-trees are RVGs, and that, any graph that can be decomposed into two caterpillar forests is an RVG. Also, they showed that any graph whose vertices of degree four or more, form a distance-two independent set is an RVG. Lastly, any graph with maximum degree four is an RVG. They also distinguished these graphs as collinear, noncollinear and weak rectangle-visibility graphs.

In 1997, Dean and Hutchinson ^{2} considered representation of bipartite graphs as rectangle- visibility graphs. They showed that for complete bipartite graphs* p **≤** q*,* Kp,q* has a representation with no rectangles having collinear side if and only if* p **≤* 2 or* p* = 3 and* q **≤* 4. More generally, Dean and Hutchinson ^{2} showed that* Kp,q* is a rectangle-visibility graph if and only if* p **≤* 4 and also that every bipartite rectangle-visibility graph on* n **≥* 4 vertices has at most 4*n **−* 12 edges. In the course of their findings they showed that, though* K*5*,*5 plus any edge, and* K*5*,*5 minus any edge are rectangle-visibility graphs;* K*5*,*5 by itself is not a rectangle-visibility graph.

Also, Kant et al.^{10}studied the area requirement of bar-visibility and rectangle-visibility representations of trees in the plane. They proved asymptotically tight lower and upper bounds on the area of such representations, and provided algorithms that construct representations with asymptotically optimal area in linear time.

In 1998, Dean et al. ^{11} considered representations of unions and products of trees as rectangle- visibility graphs. In their study, they established that the union of any tree (or forest) with a depth-1 tree is an RVG and that the union of two depth-2 trees and the union of a depth-3 tree with a matching are subgraphs of RVGs. They also showed that the cartesian product of two forests is an RVG.

Soon after, Hutchinson et al. ^{3} studied thickness-two graphs (graphs whose edge set can be partitioned into two planar subgraphs) and their representations as rectangle-visibility graphs and as doubly linear graphs (graphs that can be drawn in a plane as the union of two straight-edged planar graphs). They proved that complete graph* Kn* is an RVG if and only if* n **≤* 8. In their paper, they showed that RVGs with*n*vertices have at most 6*n**−*20 edges different from thickness two graphs with 6*n**−*12 edges.

Recently, Peterson^{5}proved results on rectangle-visibility numbers of graphs such as trees, complete graphs, complete bipartite graphs and (1*, n*)-hilly graphs which are graphs where there is no path of length 1 between vertices of degree*n*or more.

In the next Chapter, we present basic definitions and notations in graph theory and rectanglevisibility graphs.

## 3. Preliminaries

In this chapter, a brief introduction to terms and notations needed throughout this work is given. Most of these definitions are standard terms used in graph theory and rectangle-visibility graphs.

### 3.1 Definitions

The following definitions can be found in [1, 12].

Definition 3.1.1 (Graph). A*graph G*is a pair of sets (*V, E*) where*V*is the set of vertices and*E*is the set of edges.

An edge denoted as*vw*connects the vertices*v*and*w*. Two vertices*v*and*w*of a graph*G*are adjacent if there is an edge*vw*connecting them. The vertices*v*and*w*are then incident with the edge*vw*. A*loop*is an edge that connects a vertex to itself.*Parallel or multiple edges*are two or more edges that are incident to the same two vertices. The*degree of a vertex v of G*is the number of edges incident with*v*and is denoted as deg(*v*).

Definition 3.1.2 (Subgraph). A*subgraph H*= (*U, P*) of a graph*G*= (*V, E*) is a graph such that*U**⊆**V*and*P**⊆**E*.

Definition 3.1.3 (Simple graph). A*simple graph*is a graph with no parallel edges or loops.

Example 3.1.4. Figure 3.1 shows a simple graph and a non-simple graph with multiple edges. The vertex set*{a, b, d}*connected with the edges is a subgraph of the simple graph.

illustration not visible in this excerpt

Figure 3.1: A simple graph and a non-simple graph.

Now, we define several specific classes of graphs that we will use in this work.

Section 3.1. Definitions Page 7

Definition 3.1.5 (Walk and Path graphs). A* walk* in a graph G is a sequence *W* =*v*0*,e*1*,v*1*,e*2*,...,vk**−*1*,ek,vk, *

whose terms alternate between vertices and edges (not necessarily distinct) such that 1*≤**i < k*, the edge*ei*has ends*vi**−*1 and*vi*. A*path*is a walk such that all of the vertices and edges are distinct. We denote a path graph on*n*vertices by*Pn*. A typical example of a path graph is shown in Figure 3.1 of the simple graph where the path*P*:*a**→**b**→**d**→**c*.

Definition 3.1.6 (Cycle graph). A connected graph that is regular of degree 2 is a*cycle graph*. In other words, it consists of a number of vertices connected in a closed chain. A cycle graph with*n*vertices has*n*edges and is denoted by*Cn*.

Definition 3.1.7 (Complete graph). A simple graph where every pair of vertices is connected by an edge is a*complete graph*. We denote the complete graph on*n*vertices by*Kn*. A complete graph with*n*vertices has*n*(*n**−*1)*/*2 edges.

Definition 3.1.8 (Bipartite graph). A* bipartite graph* is a graph whose vertices can be separated into two disjoint sets* U* and* V* in such a way that every edge connects a vertex in* U* to a vertex in* V* .

Definition 3.1.9 (Complete bipartite graph). A*complete bipartite graph*is a bipartite graph where every vertex in set*U*is connected to every vertex in set*V*. A complete bipartite graph with*|U |*=*m*and*|V |*=*n*is denoted by*Km,n*.

Definition 3.1.10 (Star graph). A*star graph, Sn*is a connected graph on*n*vertices where one vertex has degree*n**−*1 and the other*n**−*1 vertices have degree 1. Thus, a star graph is a special case of a complete bipartite graph in which one set has 1 vertex and the other set has*n**−*1 vertices denoted by*Sn*=*K*1*,n**−*1.

(a) A complete graph*K*5. (b) A complete bipartite graph*K*3*,*3.

illustration not visible in this excerpt

Figure 3.2: Examples of a complete graph and a complete bipartite graph.

Section 3.1. Definitions Page 8

In relation to circuit design, there is a need to avoid or reduce crossing of wires since crossing leads to unwanted signals. For that matter, we define graphs that are usually used in avoiding crossing of wires.

Definition 3.1.11 (Planar and plane graphs). A graph*G*is called*plane graph*if it is drawn in the plane without any edges crossing each other. A graph which can be redrawn in a plane without any edges crossing is called a*planar graph*.

Upon drawing a plane graph it divides the plane into a set of regions known as*faces*, each bounded by edges of the graph. A face can be bounded or unbounded. We call an unbounded face the*outer or infinite face*. We denote the number of faces by*f*. Examples of infinite faces are*f*4 and*f**′*4 showninFigure^{3}.^{3}bandFigure^{3}.^{3}c.

illustration not visible in this excerpt

Figure 3.3: A plane drawing of*K*4.

Theorem 3.1.12 (Euler’s formula^{12}).*Let G be a planar drawing of a connected planar graph**and let n, m and f denote respectively the number of vertices, edges and faces of G. Then, n**−**m*+*f*= 2*.*

Let us note that not all graphs are planar. A graph which is not a planar graph is called non-planar. Examples of non-planar graphs are*K*3*,*3 and*K*5.

Definition 3.1.13 (Thickness of a graph). The thickness (*t*) of a graph (*G*) is the smallest number of planar subgraphs whose union is*G*.

Next, we present a theorem on thickness of complete graphs.

Theorem 3.1.14 (^{13}).*The thickness of a complete graph on n vertices, Kn is*

illustration not visible in this excerpt

Now, we define types of visibility graphs that are necessary in this work.

Section 3.1. Definitions Page 9

Definition 3.1.15 (Bar-visibility graphs (BVGs) ^{2}).* Bar-visibility graphs* are those planar graphs whose vertices can be represented by horizontal line segments with adjacency determined by vertical visibility. Figure 3.4 illustrates an example of a bar-visibility representation of a complete graph* K*4.

illustration not visible in this excerpt

Figure 3.4: A complete graph*K*4 and its bar-visibility representation.

Definition 3.1.16 (Rectangle-visibility graphs (RVGs)^{2}). A graph*G*is a*rectangle-visibility**graph*if its vertices can be represented by closed rectangles in the plane with sides parallel to the axes, pairwise disjoint except possibly for overlapping boundaries, in such a way that two vertices*u*and*w*are adjacent if and only if each of the corresponding rectangles is vertically or horizontally visible from the other. We call such a layout as rectangle-visibility representation which is denoted as rv-representation and an example is shown in Figure 3.5.

illustration not visible in this excerpt

Figure 3.5: A complete graph*K*4 and its rv-representation.

Definition 3.1.17 (Noncollinear rectangle-visibility representation ^{2}). A rectangle-visibility representation is called* noncollinear* if no two rectangles have collinear sides, that is, no two rectangles have endpoints with the same* x* or* y*-coordinate. We call such a layout a noncollinear rv-representation. A typical example is illustrated in Figure 3.6 whiles Figure 3.5b depicts a collinear rectangle-visibility representation.

illustration not visible in this excerpt

Figure 3.6: A complete graph*K*4 with its noncollinear rv-representation.

Definition 3.1.18 (Unit rectangle-visibility graph ^{6}). A graph* G* is a* unit rectangle-visibility * *graph or URVG* if its vertices can be represented by closed unit squares in the plane with sides parallel to axes and pairwise disjoint interiors, in such a way that two vertices are adjacent if and only if there is an unobstructed non degenerate (positive width) horizontal or vertical band of visibility joining the two rectangles. Figure 3.7 depicts a unit rectangle-visibility representation of a graph* G*.

illustration not visible in this excerpt

Figure 3.7: A graph*G*with its unit rectangle-visibility representation.

In the next Chapter, we define graph products and focus on three types of graph products. We then investigate representations of products of some classes of graphs as rectangle-visibility graphs.

**[...]**

- Quote paper
- Valentina Ocloo (Author), 2017, Rectangle-Visibility Representation of Products of Graphs, Munich, GRIN Verlag, https://www.grin.com/document/385513

Comments