Minimal Embedding Dimensions of Rectangle k-Visibility Graphs

Overview

Objectives/Goals Research on bar visibility graphs was originally motivated by problems about constructing VLSI (Very Large Scale Integration) circuits, and were adopted in the 1980s as a geometric model to represent traces, e.g. on circuit boards and in VLSI chip designs. Rectangle visibility graphs were introduced by Bose et al in 1997 as a generalization of bar visibility graphs. A graph is a rectangle visibility graph if it can be represented with vertices as disjoint axis-parallel rectangles, such that there is an unobstructed axis-parallel line of sight between two rectangles if and only if there is an edge between the corresponding vertices. I combined rectangle visibility graphs with k-visibility to form rectangle k-visibility graphs, in which the line of sight between two rectangles in the representation can be obstructed by at most k other rectangles. I then took a natural generalization of rectangle k-visibility graphs into higher dimensions. I found that given enough spacial dimensions there exists a rectangle k-visibility representation of any graph G. I continued to study its properties, and proceeded to bound it for complete graphs, complete r-partite graphs, and hypercube graphs. Results I established upper bounds on the number of dimensions needed to represent the above types of graphs as rectangle k-visibility graphs, in some cases with the added restriction that the rectangles be unit rectangles, and/or that k=0. Additionally I established a similar upper bound on the minimal embedding dimension on the Cartesian product of multiple graphs. Conclusions/Discussion The representation of graphs as hyper-rectangles with k-visibility lines is an exciting extension of existing visibility graph concepts, and like previous work in the field, is likely to have applications not yet imagined. In future research I hope to sharpen the bounds presented here, to study additional types of graphs, and to study different types of visibility.

Awards (1)

• First Place

Competition history

• CSEF 2018 Mathematical Sciences · Entry J1507

Resources

• CSEF project summary ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.

Browse more like this

• All Mathematics projects
• CSEF Mathematics projects
• Every CSEF 2018 project
• CSEF First Place winners