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.
Inhaltsverzeichnis (Table of Contents)
- Introduction
- Background of the Study
- Rationale of the Project
- Overview of the Project
- Literature Review
- Preliminaries
- Definitions
- Products of Graphs as Rectangle-Visibility Graphs
- Definitions of the types of Graph Products
- Cartesian Product
- Direct Product
- Strong Product
- Conclusion
Zielsetzung und Themenschwerpunkte (Objectives and Key Themes)
This essay explores the representation of products of different graph classes as rectangle-visibility graphs (RVGs), specifically focusing on Cartesian, direct, and strong products. It aims to provide constructive proofs for obtaining linear-time layouts of these graph products as RVGs.
- Representation of graph products as RVGs
- Linear-time layout algorithms for RVGs
- Cartesian, direct, and strong products of graphs
- Rectangle-visibility graphs and their properties
- Applications of RVGs in various fields
Zusammenfassung der Kapitel (Chapter Summaries)
- Introduction: This chapter provides a background on visibility representation of graphs, explaining the concept and its application in representing graph products. It outlines the rationale for the project, highlighting the importance of exploring RVGs for graph products, and gives an overview of the topics covered in the essay.
- Literature Review: This chapter reviews existing literature on visibility representation of graphs and relevant concepts related to graph products and RVGs. It explores previous studies and research findings, setting the context for the current work.
- Preliminaries: This chapter provides essential definitions and concepts related to graph theory and RVGs. It introduces key definitions and terminology that are used throughout the essay.
- Products of Graphs as Rectangle-Visibility Graphs: This chapter delves into the main focus of the essay, examining the representation of different graph products as RVGs. It explores the specific types of graph products (Cartesian, direct, and strong), providing constructive proofs and illustrating the linear-time layout algorithms.
Schlüsselwörter (Keywords)
Key terms and concepts in this essay include: rectangle-visibility graph (RVG), cartesian product, direct product, strong product, graph products, visibility representation, linear-time layout, constructive proofs.
Frequently Asked Questions
What is a Rectangle-Visibility Graph (RVG)?
An RVG is a graph where vertices are represented as rectangles in a plane, and edges exist between them if they can "see" each other horizontally or vertically.
Which types of graph products are explored in this work?
The research focuses on three main types: Cartesian products, direct products, and strong products of various graph classes.
Can all graph products be represented as RVGs?
The study investigates specific classes like paths, cycles, stars, and complete graphs, and also discusses why some complete graphs cannot be represented as RVGs.
What are the practical results of this research?
The results are established through constructive proofs that yield linear-time layout algorithms for representing these graph products.
What is the significance of visibility representation?
It provides a geometric way of visualizing graph structures, which is useful in fields like VLSI design and network visualization.
- Quote paper
- Valentina Ocloo (Author), 2017, Rectangle-Visibility Representation of Products of Graphs, Munich, GRIN Verlag, https://www.grin.com/document/385513
