Unit BarVisibility Layouts of Triangulated Polygons Extended AbstractDean, Alice M. and Gethner, Ellen and Hutchinson, Joan P. (2004) Unit BarVisibility Layouts of Triangulated Polygons Extended Abstract. In: Graph Drawing 12th International Symposium, GD 2004, September 29October 2, 2004 , pp. 111121(Official URL: http://dx.doi.org/10.1007/9783540318439_13). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783540318439_13
AbstractA triangulated polygon is a 2connected maximal outerplanar graph. A unit barvisibility graph (UBVG for short) is a graph whose vertices can be represented by disjoint, horizontal, unitlength bars in the plane so that two vertices are adjacent if and only if there is a nondegenerate, unobstructed, vertical band of visibility between the corresponding bars. We give combinatorial and geometric characterizations of the triangulated polygons that are UBVGs. To each triangulated polygon G we assign a character string with the property that G is a UBVG if and only if the string satisfies a certain regular expression. Given a string that satisfies this condition, we describe a lineartime algorithm that uses it to produce a UBV layout of G.
Actions (login required)
