Rectangle-Visibility Representation of Products of Graphs

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

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.