Open RectangleofInfluence Drawings of Inner Triangulated Plane GraphsMiura, Kazuyuki and Matsuno, Tetsuya and Nishizeki, Takao (2007) Open RectangleofInfluence Drawings of Inner Triangulated Plane Graphs. In: Graph Drawing 14th International Symposium, GD 2006, September 1820, 2006 , pp. 138149(Official URL: http://dx.doi.org/10.1007/9783540709046_15). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783540709046_15
AbstractA straightline drawing of a plane graph is called an open rectangleofinfluence drawing if there is no vertex in the proper inside of the axisparallel rectangle defined by the two ends of every edge. In an inner triangulated plane graph, every inner face is a triangle although the outer face is not always a triangle. In this paper, we first obtain a sufficient condition for an inner triangulated plane graph G to have an open rectangleofinfluence drawing; the condition is expressed in terms of a labeling of angles of a subgraph of G. We then present an O(n^{1.5}/log n)time algorithm to examine whether G satisfies the condition and, if so, construct an open rectangleofinfluence drawing of G on an (n1) x (n1) integer grid, where n is the number of vertices in G.
Actions (login required)
