Narrow Results

Irreducible triangulations are plane graphs with a quadrangular exterior face, triangular interior faces and no separating triangles. Fusy proposed a straight-line grid drawing algorithm for irreducible triangulations, whose grid size is asymptotically with high probability 11n/27 × 11n/27 up to an additive error of . Later on, Fusy generalized the idea to quadrangulations and obtained a straight-line grid drawing, whose grid size is asymptotically with high probability 13n/27 × 13n/27 up to an additive error of . In this paper, we first prove that the above two straight-line grid drawing algorithms for irreducible triangulations and quadrangulations actually produce open rectangle-of-influence drawings for them respectively. Therefore, the above mentioned straight-line grid drawing size bounds also hold for the open rectangle-of-influence drawings. These results improve previous known drawing sizes.

In the second part of the paper, we present another application of the results obtained by Fusy. We present a linear time algorithm for constructing a rectangular dual for a randomly generated irreducible triangulation with n vertices, one of its dimensions equals asymptotically with high probability, up to an additive error of . In addition, we prove that the one dimension tight bound for a rectangular dual of any irreducible triangulations with n vertices is (n + 1)/2.

Although rectangular dualization has been studied for several years in the context of floorplanning problems, its descriptive power has not been fully exploited for graph representation. The main obstacle is that the computation of a rectangular dual of any planar biconnected graph requires a sequence of non-trivial steps, some of which are still under investigation. In particular, the most tricky issue is the optimal management of separating triangles, for which no existing algorithm runs in linear time. In this paper we present our advances in rectangular dualization and we show two applications that, while very different, explain better than others its role.

A rectangular dual D of a planar graph G is a planar embedding of a dual graph of G such that all inner faces and the total graph enclosure are rectangular. Regarding each inner face of a rectangular dual as an area for a functional block to be placed, we can use the rectangular dual for a floorplan of a VLSI. If a planar graph G representing a given VLSI circuit contains a complex triangle (a cycle of length three which is not a boundary of a face), then G does not have a rectangular dual. Therefore, such complex triangles must be eliminated from G.

This paper proposes a heuristic algorithm to this problem, which is to find a minimal set E* of edges such that all complex triangles of a given planar graph are eliminated by changing each edge of E* to two serial edges. The algorithm has the time complexity of O(|V|2) and a constant worst-case performance ratio of 2, where V is a set of vertices.