First Advisor

John S. Caughman

Date of Award

Winter 3-2022

Document Type


Degree Name

Bachelor of Science (B.S.) in Mathematics and University Honors


Mathematics and Statistics




visibility representation, bar visibility graph, VLSI, line-of-sight graph, integer bar visibility graph, bar-representable graph


A visibility representation is an association between the set of vertices in a graph and a set of objects in the plane such that two objects have an unobstructed, positive-width line of sight between them if and only if their two associated vertices are adjacent. In this paper, we focus on integer bar visibility graphs (IBVGs), which use horizontal line segments with integer endpoints to represent the vertices of a given graph. We present results on the exact widths of IBVGs of paths, cycles, and stars, and lower bounds on trees and general graphs. In our main results, we find a necessary condition for a graph to have width k.


In Copyright. URI: This Item is protected by copyright and/or related rights. You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s).

Persistent Identifier