Philippine E-Journals

An Integral Planar Embedding of Graphs

Severino V. Gervacio | Leonor Aquino-ruivivar

Discipline: Mathematics

 

Abstract:

It is always possible to choose n distinct points in the plane to represent the vertices of a graph of order n such that whenever two vertices are adjacent, then the distance between the corresponding points is an integer. Furthermore, the edge joining two adjacent vertices is represented by the line segment joining the points corresponding to the vertices. Adding the restriction that two edges have at most one point in common implies that the edges can cross one another but they cannot overlap. It is the objective of this paper to look for a representation of the graph which is contained in as small a closed disk as possible. It proves that a representation for the complete graph of order n, and hence for any graph of order n, can be contained in a closed disk of diameter 5[n/2].