Search

A rectilinear dual of a plane graph refers to a partition of a rectangular area into nonoverlapping rectilinear polygonal modules, where each module corresponds to a vertex such that two modules have a side-contact iff their corresponding vertices are adjacent. An interesting observation is that most algorithms yielding low polygonal complexity rectilinear duals require the use of ⊤-shape modules or their extensions. To justify the intuition that ⊤-shape modules are more powerful than other 8-sided modules, we show the optimum polygonal complexity of ⊤-free rectilinear duals to be exactly 12. Our construction uses only monotone staircase modules. We continue this line of research by studying polygonal complexity and area-universality of rectilinear duals using modules of constrained shapes. Motivated by the design challenges in 3D IC technology, we also study the generalization of rectilinear duals in three dimensions by allowing each module to be an orthogonal polyhedron. Such a generalization to three dimensions opens the door for non-planar graphs to be accommodated in floorplan design. In particular, we prove that all chordal graphs admit 3D floorplans, which parallels the well-known result that all maximal plane graphs admit rectilinear duals. [ABSTRACT FROM AUTHOR]

Abstract: The conventional force-directed methods for drawing undirected graphs are based on either vertex–vertex repulsion or vertex–edge repulsion. In this paper, we propose a new force-directed method based on edge–edge repulsion to draw graphs. In our framework, edges are modelled as charged springs, and a final drawing can be generated by adjusting positions of vertices according to spring forces and the repulsive forces, derived from potential fields, among edges. Different from the previous methods, our new framework has the advantage of overcoming the problem of zero angular resolution, guaranteeing the absence of any overlapping of edges incident to the common vertex. Given graph layouts probably generated by previous algorithms as the inputs to our algorithm, experimental results reveal that our approach produces promising drawings not only preserving the original properties of a high degree of symmetry and uniform edge length, but also preventing zero angular resolution and usually having larger average angular resolution. However, it should be noted that exhibiting a higher degree of symmetry and larger average angular resolution does not come without a price, as the new approach might result in the increase in undesirable overlapping of vertices as some of our experimental results indicate. To ease the problem of node overlapping, we also consider a hybrid approach which takes into account both edge–edge and vertex–vertex repulsive forces in drawing a graph. [Copyright &y& Elsevier]

Assume that there are players and an eavesdropper Eve, where several pairs of players have shared secret keys beforehand. We regard each player as a vertex of a graph and regard each pair of players sharing a key as an edge. Consider the case where Eve knows some of the keys according to a certain probability distribution. In this paper, applying the technique of st-numbering, we propose a protocol which allows any two designated players to agree on a secret key through such a "partially leaked key exchange graph." Our protocol is optimal in the sense that Eve's knowledge about the secret key agreed on by the two players is as small as possible. [ABSTRACT FROM AUTHOR]