Rectangle-Visibility Representation of Products of Graphs

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 ofK

3.4 A complete graphK4 and its bar-visibility representation.

3.5 A complete graphK4 and its rv-representation

3.6 A complete graphK4 with its noncollinear rv-representation

3.7 A graphGwith its unit rectangle-visibility representation

4.1 Construction ofP3×P

4.2 A rv-representation ofP3×P

4.3 Construction ofP4×P4 and its rv-representation

4.4 A rv-representation ofPm×Pn

4.5 Construction ofC3×C3 and its rv-representation

4.6 Construction ofC6×P2 and its rv-representation

4.7 Construction ofC5×P3 and its rv-representation

4.8 A rv-representation ofCm×Pn

4.9 Construction ofS8×P2 and its rv-representation

4.10 Construction ofS9×P2 and its rv-representation

4.11 Construction ofK4×K2 and its rv-representation

4.12 Construction ofP3□P3 with its rv-representation

4.13 Construction ofP5□P3 with its rv-representation

4.14 Construction ofC3□C3 and its rv-representation

4.15 Construction ofC6□P2 and its rv-representation

4.16 Construction ofC5□P2 and its rv-representation

4.17 Construction ofK4□K2 and its rv-representation

4.18 Construction ofP3 ⊠P2 with its rv-representation

4.19 Construction ofP3 ⊠P3 with its rv-representation

4.20 Construction ofC3 ⊠P2 and its rv-representation

4.21 Construction ofC4 ⊠P2 and its rv-representation

4.22 Construction ofK4 ⊠K2 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 ¹. 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 ².

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³. Hence, we say such graphs have thickness at most two. Shermer⁴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 ⁵. 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 ⁵.

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⁶. 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⁶. 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. ⁷. 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⁸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 ⁷. Bose et al. ⁹ 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 ² 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 ² 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 4n − 12 edges. In the course of their findings they showed that, though K5,5 plus any edge, and K5,5 minus any edge are rectangle-visibility graphs; K5,5 by itself is not a rectangle-visibility graph.

Also, Kant et al.¹⁰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. ¹¹ 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. ³ 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 withnvertices have at most 6n−20 edges different from thickness two graphs with 6n−12 edges.

Recently, Peterson⁵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 degreenor 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). Agraph Gis a pair of sets (V, E) whereVis the set of vertices andEis the set of edges.

An edge denoted asvwconnects the verticesvandw. Two verticesvandwof a graphGare adjacent if there is an edgevwconnecting them. The verticesvandware then incident with the edgevw. Aloopis an edge that connects a vertex to itself.Parallel or multiple edgesare two or more edges that are incident to the same two vertices. Thedegree of a vertex v of Gis the number of edges incident withvand is denoted as deg(v).

Definition 3.1.2 (Subgraph). Asubgraph H= (U, P) of a graphG= (V, E) is a graph such thatU⊆VandP⊆E.

Definition 3.1.3 (Simple graph). Asimple graphis 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 =v0,e1,v1,e2,...,vk−1,ek,vk,

whose terms alternate between vertices and edges (not necessarily distinct) such that 1≤i < k, the edgeeihas endsvi−1 andvi. Apathis a walk such that all of the vertices and edges are distinct. We denote a path graph onnvertices byPn. A typical example of a path graph is shown in Figure 3.1 of the simple graph where the pathP:a→b→d→c.

Definition 3.1.6 (Cycle graph). A connected graph that is regular of degree 2 is acycle graph. In other words, it consists of a number of vertices connected in a closed chain. A cycle graph withnvertices hasnedges and is denoted byCn.

Definition 3.1.7 (Complete graph). A simple graph where every pair of vertices is connected by an edge is acomplete graph. We denote the complete graph onnvertices byKn. A complete graph withnvertices hasn(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). Acomplete bipartite graphis a bipartite graph where every vertex in setUis connected to every vertex in setV. A complete bipartite graph with|U |=mand|V |=nis denoted byKm,n.

Definition 3.1.10 (Star graph). Astar graph, Snis a connected graph onnvertices where one vertex has degreen−1 and the othern−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 hasn−1 vertices denoted bySn=K1,n−1.

(a) A complete graphK5. (b) A complete bipartite graphK3,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 graphGis calledplane graphif 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 aplanar graph.

Upon drawing a plane graph it divides the plane into a set of regions known asfaces, each bounded by edges of the graph. A face can be bounded or unbounded. We call an unbounded face theouter or infinite face. We denote the number of faces byf. Examples of infinite faces aref4 andf′4 showninFigure³.³bandFigure³.³c.

illustration not visible in this excerpt

Figure 3.3: A plane drawing ofK4.

Theorem 3.1.12 (Euler’s formula¹²).Let G be a planar drawing of a connected planar graphand 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 areK3,3 andK5.

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

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

Theorem 3.1.14 (¹³).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) ²). 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 K4.

illustration not visible in this excerpt

Figure 3.4: A complete graphK4 and its bar-visibility representation.

Definition 3.1.16 (Rectangle-visibility graphs (RVGs)²). A graphGis arectangle-visibilitygraphif 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 verticesuandware 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 graphK4 and its rv-representation.

Definition 3.1.17 (Noncollinear rectangle-visibility representation ²). 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 graphK4 with its noncollinear rv-representation.

Definition 3.1.18 (Unit rectangle-visibility graph ⁶). 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 graphGwith 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.

[...]