Visibility graphs

Table of contents

Induced visibility graphs

The following problem is due to J. Spinrad

A graph G is called a visibility graph if there is a polygon P such that the vertices of P are the vertices of G, and two vertices are adjacent in G if they are visible in P. A graph H is called an induced visibility graph if there is a polygon P such that H is an induced subgraph of the visibility graph VG(P) of P. Observe that an induced visibility graph may not necessarily be the visibility graph of a polygon. For example, a cycle with five vertices is not a visibility graph, however it is an induced visibility graph.

The cycle with five vertices is an induced subgraph of the 10 vertex polygon shown here.

If H has n vertices, what is the smallest m such that H is an induced visibility graph of a polygon with m vertices?

Spinrad affirms: I know that m is O(nlognalpha(n)), but it could well be O(n)?.

Representations of visibility graphs

The following problem is due to J. Spinrad

Problem: Variant of a well known problem: Is there a representation of visibility graphs which uses O(logn) bits per vertex, such that adjacency between any two vertices x and y can be tested using only the bits stored at x and y ? Either a proof or disproof would be interesting.

A la página principal de problemas abiertos . A mi página.

Jorge Urrutia,
Instituto de Matemáticas,
Universidad Nacional Autónoma de México
urrutia@matem.unam.mx
School of Information Technology and Engineering
University of Ottawa,
jorge@site.uottawa.ca

A la página del Instituto de Matemáticas