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 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 |