Open Rectangle-of-Influence Drawings of Inner Triangulated Plane Graphs

Miura, Kazuyuki and Matsuno, Tetsuya and Nishizeki, Takao (2007) Open Rectangle-of-Influence Drawings of Inner Triangulated Plane Graphs. In: Graph Drawing 14th International Symposium, GD 2006, September 18-20, 2006 , pp. 138-149(Official URL:

Full text not available from this repository.


A straight-line drawing of a plane graph is called an open rectangle-of-influence drawing if there is no vertex in the proper inside of the axis-parallel 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 rectangle-of-influence 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 rectangle-of-influence drawing of G on an (n-1) x (n-1) integer grid, where n is the number of vertices in G.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-540-70904-6_15
Classifications: P Styles > P.720 Straight-line

Actions (login required)

View Item View Item