1-3hit |
A new approach for topological routing is proposed by W-graph. We employ a W-graph Gw(V, E, W) for indicating all nets which will be assigned to two-layer, where V is a set of all terminals, E is a set of edges corresponding to two-terminal nets and W is a set of wild components corresponding to multi-terminal nets. Such that the topological routing problem can be considered as: Given a circle H containing V in the sequence corresponding to terminals on the boundary of routing region, then drawing H Gw on a plane with minimum number of created vertices (crossing points on H).
A W-graph is a partially known graph which contains wild-components. A wild-component is an incompletely defined connected subgraph having p vertices and p-1 unspecified edges. The informations we know on a wild-component are which has a vertex set and between any two vertices there is one and only one path. In this paper, we discuss the properties of circuits in a W-graph (called W-circuits). Although a W-graph has unspecified edges, we can obtain some important properties of W-circuits. We show that the W-ring sum of W-circuits is also a W-circuit in the same W-graph. The following (1) and (2) are proved: (1) A W-circuit Ci of a W-graph can be transformed into either a circuit or an edge disjoint union of circuits, denoted by Ci*, of a graph derived from the W-graph, (2) if W-circuits C1, C2,
We will introduce W-trees of a W-graph which is a graph containing wild components. A wild component is an incompletely defined subgraph which is known to be a tree but what kind of the tree is unspecified. W-tree is defined as a set of edges and vertices of wild components obtained from a non-sigular major submatrix of a W-incidence matrix. The properties of a W-tree are useful for studying linear independent W-cutsets and so on in a W-graph.