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.
Contents
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
Objectives and Topics
This essay explores the feasibility of representing products of various graph classes as rectangle-visibility graphs (RVGs). By investigating three fundamental types of graph products—cartesian, direct, and strong—the work seeks to classify which of these structures can be embedded into a plane as RVGs, with specific focus on paths, cycles, stars, and complete graphs.
- Theoretical definitions of visibility representations and graph products.
- Construction of rectangle-visibility layouts for cartesian product graphs.
- Analysis of direct product graphs as rectangle-visibility representations.
- Investigation of strong product graph properties regarding rectangle visibility.
- Case studies on the non-existence of RVG representations for certain complete graphs.
Auszug aus dem Buch
4.2 Cartesian Product
In the cartesian product, Dean et al. [11] established on rectangle-visibility representations for products of graphs as given below.
Theorem 4.2.1 ([11]). If the graphs G and H are both BVGs, then G x H is an RVG. Analogous statements hold if G and H are noncollinear or weak BVGs.
With regards to the two graphs being BVGs, Tamassia and Tollis [8] showed that BVGs are planar graphs but not all planar graphs are BVGs. Hence, if G is the cartesian product of two planar graphs, then G has thickness at most 2 which follows that G is an RVG. The following results, though discovered independently, can be stated as corollaries to Theorem 4.2.1 and we give some illustrative examples. We start with cartesian product for path graphs.
Path graph: We construct the cartesian product for P3 x P2 and P4 x P4. In Figure 4.1 of the construction of P3 x P2, the vertex set V(P3) x V(P2) = {(a, 1), (b, 1), (c, 1), (a, 2), (b, 2), (c, 2)}. Consider vertices (a, 1) and (b, 1), since 1 = 1 and a is adjacent to b in the graph (P3), we put an edge between (a, 1) and (b, 1). Hence by adding the edges in that manner, we obtain a grid graph as shown in Figure 4.1. Since (b, 1) is adjacent to (a, 1), (c, 1) and (b, 2) in the grid graph (P3 x P2), we represent each vertex as a rectangle of equal size and place the rectangle in a way that it is visible by its adjacency. At the end of the arrangement, we obtain an rv-representation in Figure 4.2.
Summary of Chapters
1. Introduction: Provides the historical context of graph theory and defines the scope of rectangle-visibility graphs within the framework of VLSI design.
2. Literature Review: Surveys existing research on visibility representations and the classification of graphs that qualify as rectangle-visibility graphs.
3. Preliminaries: Establishes fundamental graph-theoretic definitions and notations required for the constructions presented in the subsequent chapters.
4. Products of Graphs as Rectangle-Visibility Graphs: Examines how cartesian, direct, and strong products of various graph classes behave in terms of their visibility representations, supported by constructive proofs.
5. Conclusion: Summarizes the findings regarding the classification of product graphs as RVGs and suggests directions for future research.
Keywords
Rectangle-visibility graph, cartesian product, direct product, strong product, graph theory, VLSI design, visibility representation, planar graphs, complete graphs, path graphs, cycle graphs, star graphs, graph construction, layout algorithms, thickness-two graphs.
Frequently Asked Questions
What is the core subject of this research?
The research focuses on the representation of product graphs as rectangle-visibility graphs (RVGs), which are geometric layouts where vertices are mapped to rectangles and edges are defined by horizontal or vertical visibility.
Which types of graph products are examined?
The essay investigates three primary types of graph products: the cartesian product, the direct product, and the strong product.
What is the primary research goal?
The objective is to determine and classify which specific products of fundamental graph classes (such as paths, cycles, and complete graphs) can be represented as rectangle-visibility graphs.
What methodology is employed to arrive at the results?
The work utilizes constructive proof methods, creating specific layouts for various graph products to demonstrate their status as RVGs, while also referencing thickness constraints for non-RVG instances.
What is covered in the main body of the work?
The main body systematically applies these visibility rules to different product categories, providing detailed constructions, figures, and illustrative examples for each graph product type.
How would you summarize the work in a few keywords?
The work is defined by terms such as Rectangle-visibility graph, graph products (cartesian, direct, strong), VLSI design, and visibility representations.
Why are complete graphs sometimes excluded from being RVGs?
Complete graphs often exceed the required "thickness-two" property for RVGs; as the number of vertices increases, the number of edges becomes too high to maintain valid visibility representation in a plane.
What is the significance of the "thickness" of a graph in this study?
Thickness represents the minimum number of planar subgraphs whose union forms the graph; this is crucial because an RVG layout implies a graph can be decomposed into at most two planar visibility layers.
- Quote paper
- Valentina Ocloo (Author), 2017, Rectangle-Visibility Representation of Products of Graphs, Munich, GRIN Verlag, https://www.grin.com/document/385513
