8279644
Z-transformation graphs of maximum matchings of plane bipartite graphs
Let G be a plane bipartite graph. The Z-transformation graph Z(G) and its orientation Z(G) on the maximum matchings of G are defined. If G has a perfect matching, Z(G) and Z(G) are the usual Z-transformation graph and digraph. If G has neither isolated vertices nor perfect matching, then Z(G) is not connected. This paper mainly shows that some basic results for Z-transformation graph (digraph) of a plane elementary bipartite graph still hold for every nontrivial component of Z(G) (Z(G)). In particular, by obtaining a result that every shortest path of Z(G) from a source of Z(G) corresponds to a directed path of Z(G), we show that every nontrivial component of Z(G) has exactly one source and one sink. Accordingly, it follows that the block graph of every nontrivial component of Z(G) is a path. In addition, we give a simple characterization for a maximum matching of G being a cut-vertex of Z(G).
44874837
Z-transformation graphs of perfect matchings of plane bipartite graphs
Abstract Let G be a plane bipartite graph with at least two perfect matchings. The Z -transformation graph, Z F ( G ), of G with respect to a specific set F of faces is defined as a graph on the perfect matchings of G such that two perfect matchings M 1 and M 2 are adjacent provided M 1 and M 2 differ only in a cycle that is the boundary of a face in F . If F is the set of all interior faces, Z F ( G ) is the usual Z -transformation graph; If F contains all faces of G it is a novel graph and called the total Z -transformation graph. In this paper, we give some simple characterizations for the Z -transformation graphs to be connected by applying the above new idea. Furthermore, we show that the total Z -transformation graph of G is 2-connected if G is elementary; the total Z -transformation digraph of G is strongly connected if and only if G is elementary.
46427487
The Clar Covering Polynomial of Hexagonal Systems I
Abstract In this paper the Clar covering polynomial of a hexagonal system is introduced. In fact it is a kind of F polynomial [4] of a graph, and can be calculated by recurrence relations. We show that the number of aromatic sextets (in a Clar formula), the number of Clar formulas, the number of Kekule structures and the first Herndon number for any Kekulean hexagonal system can be easily obtained by its Clar covering polynomial. In addition, we give some theorems to calculate the Clar covering polynomial of a hexagonal system. As examples we finally derive the explicit expressions of the Clar covering polynomials for some small hexagonal systems and several types of catacondensed hexagonal systems. A relation between the resonance energy and the Clar covering polynomial of a hexagonal system is considered in the next paper.
41201857
A Note on the Number of Perfect Matchings of Bipartite Graphs
Abstract Let G be a bipartite graph with 2n vertices, A its adjacency matrix and K the number of perfect matchings. For plane bipartite graphs each interior face of which is surrounded by a circuit of length 4s + 2, s ϵ {1, 2, …}, an elegant formula, i.e. det A = (−1)nK2, had been rigorously proved by Cvetkovic et al. (1982). For general bipartite graphs, this note contains a necessary and sufficient condition for the above relation to hold. A fast algorithm to check if a plane bipartite graph has such a relation is given.
17799789
Cell rotation graphs of strongly connected orientations of plane graphs with an application
The cell rotation graph D(G) on the strongly connected orientations of a 2-edge-connected plane graph G is defined. It is shown that D(G) is a directed forest and every component is an in-tree with one root; if T is a component of D(G), the reversions of all orientations in T induce a component of D(G), denoted by T-, thus (T,T-) is called a pair of in-trees of D(G); G is Eulerian if and only if D(G) has an odd number of components (all Eulerian orientations of G induce the same component of D(G)); the width and height of T are equal to that of T-, respectively. Further it is shown that the pair of directed tree structures on the perfect matchings of a plane elementary bipartite graph G coincide with a pair of in-trees of D(G). Accordingly, such a pair of in-trees on the perfect matchings of any plane bipartite graph have the same width and height.
29766053
Construction for bicritical graphs and k-extendable bipartite graphs
A graph G is said to be bicritical if G-u-v has a perfect matching for every choice of a pair of points u and v. Bicritical graphs play a central role in decomposition theory of elementary graphs with respect to perfect matchings. As Plummer pointed out many times, the structure of bicritical graphs is far from completely understood. This paper presents a concise structure characterization on bicritical graphs in terms of factor-critical graphs and transversals of hypergraphs. A connected graph G with at least 2k+2 points is said to be k-extendable if it contains a matching of k lines and every such matching is contained in a perfect matching. A structure characterization for k-extendable bipartite graphs is given in a recursive way. Furthermore, this paper presents an O(mn) algorithm for determining the extendability of a bipartite graph G, the maximum integer k such that G is k-extendable, where n is the number of points and m is the number of lines in G.
37845872
The complexity of learning in PLN networks
Abstract In this paper, the complexity of learning in the feedforward PLN network is investigated by using Markov chain theory, when its training samples are incomplete (i.e., a network with hidden nodes). We present a learning algorithm. A formula for computing the average number of steps that the learning algorithm converges is obtained when the PLN network exists a solution. In the probabilistic sense, the completeness of the learning algorithm is proved. Some computer simulations are given to verify the analysis.
8107037
Forward Shadow Mapping
Forward shadow mapping is a new approach to real-time shadow generation. The traditional shadow map algorithm maps the pixels in the eye’s view backward into the depth buffers of light sources (i.e. shadow maps), which is similiar to and often implemented as an extension to texture mapping. Our algorithm reverses this process by using 3-D image warping techniques to transform shadow map pixels forward into the eye’s view to directly indicate which pixels are lit; it does not interfere with normal texture mapping and easily supports antialiased shadow edges and projective textures. Access to shadow maps and projective textures is in pixel-sequential order. This algorithm has advantages when speed of texture mapping becomes the performance bottleneck, which is often the case in visual simulation and game applications.
940067
Visibility representation of plane graphs via canonical ordering tree,
In a visibility representation (VR for short) of a plane graph G, each vertex of G is represented by a horizontal line segment such that the line segments representing any two adjacent vertices of G are joined by a vertical line segment. Rosenstiehl and Tarjan [Rectilinear planar layouts and bipolar orientations of planar graphs, Discrete Comput. Geom. 1 (1986) 343], Tamassia and Tollis [An unified approach to visibility representations of planar graphs, Discrete Comput. Geom. 1 (1986) 321] independently gave linear time VR algorithms for 2-connected plane graph. Afterwards, one of the main concerns for VR is the size of the representation. In this paper, we prove that any plane graph G has a VR with height bounded by ⌊5n/6⌋. This improves the previously known bound ⌊15n/16⌋. We also construct a plane graph G with n vertices where any VR of G requires a size of (⌊2n/3⌋) × (⌊4n/3⌋ - 3). Our result provides an answer to Kant's open question about whether there exists a plane graph G such that all of its VR require width greater that cn, where c > 1 [G. Kant, A more compact visibility representation, Internat. J. Comput. Geom. Appl. 7 (1997) 197].
18261046
Shelling Algorithm in Solid Modeling
Shelling is a powerful modeling operation in current CAD /CAM systems. In this paper, we present a new shelling algorithm for regular B-Rep solids. We first generate an initial offset solid, then correct the self-intersecting offset solid if necessary. We obtain the resultant shelling solid through a regularized Boolean operation finally. The algorithm has been implemented in a solid modeling system, and some examples are given to illustrate it.
39496103
An Application of Well-orderly Trees in Graph Drawing
Well-orderly tree is a powerful technique capable of deriving new results in graph encoding, graph enumeration and graph generation [3, 5]. In this paper, by using well-orderly trees, we prove that any plane graph G with n vertices has a visibility representation with height , which can be constructed in linear time. This improves the best previous bound of .