A note on visibility graphs (Q1099193): Difference between revisions

Let \(S=\{s_ 1,...,s_ n\}\), \(n\geq 1\), be a set of disjoint vertical straight line segments in a plane. Each \(s_ i\) connects two extreme points \((x_ i,a_ i)\), \((x_ i,b_ i)\), \(a_ i<b_ i\). Assume that \(x_ 1<x_ 2<...<x_ n\) and \(a_ i\neq a_ j\), \(a_ i\neq b_ j\), \(b_ i\neq b_ j\), for \(i\neq j\). We say that \(s_ i\) and \(s_ j\) see each other if there is a horizontal line segment which intersects them, but does not intersect any other line segment between them. A visibility graph G can be constructed on vertices \(v_ 1,...,v_ n\) such that \(v_ i\) and \(v_ j\) are joined by an edge if the corresponding segments \(s_ i\) and \(s_ j\) see each other. It is proved that any visibility graph G can be transformed by successive duplications of existing edges of G into a planar multigraph with all triangular finite faces. Conversely, any such graph is a visibility graph for some set S.