On some properties of the intersection graph of half-planes induced by a set of lines

Date of Publication

2007

Document Type

Bachelor's Thesis

Degree Name

Bachelor of Science in Mathematics

College

College of Science

Department/Unit

Mathematics and Statistics

Defense Panel Chair

Severino V. Gervacio

Defense Panel Member

Yvette F. Lim
Mark Anthony A. Garcia

Abstract/Summary

This study presents some properties of the intersection graph of a finite set of half-planes induced by a set of lines. The results are divided into two parts. The first part, which appears in Chapter 3, gives some of the properties of the graph G(Ln). Most of the results presented here are original results by the researchers. The second part, which is contained in Chapter 4, is an exposition of the first two sections of the paper entitled "On the Intersection Graphs of Halfplanes and of Line Segments in the Plane" by Dr. Severino Gervacio. It includes a characterization for a graph to be the intersection graph of a set of half-planes using the notion of neighborhood-ordered graphs.

The study also includes a program which implements the results of the paper by Dr. Gervacio. Given a user-input graph, the program determines if the graph can be represented as the intersection graph of a given set of half-planes and if so, it proceeds to generate such a set of half-planes.

Abstract Format

html

Language

English

Format

Print

Accession Number

TU14187

Shelf Location

Archives, The Learning Commons, 12F, Henry Sy Sr. Hall

Physical Description

1 v. (various foliations) : ill.

Keywords

Graph theory

This document is currently not available here.

Share

COinS