A Study of Bar and Arc k-Visibility Graphs

Overview

Bar Visibility Graphs were introduced by Duchet et al. and Schlag et al. to model Very Large Scale Integration (VSLI), the process by which billions of transistors are wired together on a single chip. In particular, Bar Visibility Graphs record the direct vertical visibilities between a given set of horizontal bars. Dean et al., Babbitt et al. and Hutchison generalized Bar Visibility Graphs to Bar and Arc k-Visibility Graphs. In this project the maximal number of edges in an Arc k-Visibility Graph with n vertices is improved to at most (k+1)(3n-(3k+6)/2) edges for n>4k+4 and (n)(n-1)/2 for n<4k+5. Then the maximal edge bound given in Babbitt et al. for SemiArc k-Visibility Graph is shown to be optimal, disproving a conjecture given by Babbitt et al. Additionally this project makes progress towards classifying Bar k-Visibility Graphs by proving that a family of Bar i-Visibility Graphs is never contained in a family of Bar j-Visibility Graphs for i not equal to j. Finally the concept of random Visibility Graphs are introduced and the expected number of edges in a SemiBar k-Visibility Graph is calculated.

Competition history

• ISEF 2016 Category not listed · Entry MATH011

Resources

• ISEF abstract page ↗

Related projects

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