Aspect graphs: An introduction and survey of recent results

The study of the aspect graph of a three-dimensional object has recently become an active area of research in computer vision. The aspect graph provides a complete enumeration of all possible distinct views of an object, given a model for viewpoint space and a definition for “distinct.” This article presents a tutorial introduction to the aspect graph, surveys the current state of the art in algorithms for automatically constructing aspect graphs, and describes some possible applications of aspect graphs in computer vision and computer graphics.     

节点与决策模式两段式映射的子图查询算法

针对大规模图集的子图查询问题,给出了一种基于节点与决策模式映射(NDFM)的索引结构——NDFM-Index,并在此索引结构的基础上提出了一种图集的子图查询算法。NDFM-Index利用图中关键节点所携带的结构信息以及邻居的标号分布,与决策模式形成映射,从而不通过枚举直接得到查询图所包含的索引模式,得到更小的候选集。理论与实验的分析结果表明,该算法不但能避免索引筛选过程中对查询图子图的枚举过程,而且能显著地减小候选集尺寸,进而大大降低查询图与候选集之间的子图同构测试次数,提高查询效率。     

The Vertex Splitting Algorithm for facilities layout

The graph theoretic facility layout problem (GTFLP) seeks the best spatial arrangement of a set of facilities, which minimizes the total transportation cost of material flow between facilities, or maximizes total facility adjacency benefits. The GTFLP has applications in arranging rooms within a building floorplan, placing machines on a factory floor, controls on an instrument panel, or components on a circuit board. For this reason, the GTFLP is an important problem within industrial design. The GTFLP comprises two phases: the generation of a highly weighted maximal planar graph (MPG), whose edges specify adjacencies required in the layout, and the drawing of an orthogonal geometric dual to this MPG, called the block plan, under given area requirements for each facility. The first phase is NP-complete, and has been researched extensively; in the absence of a polynomial time algorithm, it appears there is little future for further research in this area. The second phase however has received far less attention due to the difficulties in not only determining algorithms for generating layouts, but also the hurdles encountered in automating these methods. This paper presents a new approach to finding a block plan from an arbitrary MPG, with facility area requirements.     

图的森林图

本文中引进了连通图的森林图,它是树图的推广.研究了森林图的子图：邻接森林图和叶交换森林图.特别,邻接树图和线图是我们推广的特殊情况.进而,我们研究了这些图的性质并提出了可进一步研究的问题.     

On converting a dual graph into a block layout

One of the difficulties associated with the application of graph theory to the facilities layout problem is the conversion of the dual graph into a block layout. This paper presents a procedure to address this problem. The procedure exploits the similarities between the graph-theoretic approach and computerized layout-construction procedures, and also resolves some of their differences. It considers the faces of the dual graph one by one and places them in the block layout adjacent to each other in a manner consistent with the adjacencies specified by the dual graph, The procedure is independent.of the manner the maximal planar weighted graph is developed.     

Delayed recognition of Judah Folkman’s hypothesis on tumor angiogenesis: when a Prince awakens a Sleeping Beauty by self-citation

In research evaluation of single researchers, the assessment of paper and journal impact is of interest. High journal impact reflects the ability of researchers to convince strict reviewers, and high paper impact reflects the usefulness of papers for future research. In many bibliometric studies, metrics for journal and paper impact are separately presented. In this paper, we introduce two graph types, which combine both metrics in a single graph. The graphs can be used in research evaluation to visualize the performance of single researchers comprehensively.     

Robust multi-planar region detection for image mosaic based on hierarchical clustering mechanism

Abstract

Planar structures exist widely in the images of various scenes, and the detection of planar regions is important in many applications related to computer vision, such as image mosaic and three-dimensional reconstruction. In this paper, a robust detection method for multi-planar regions is proposed. After the feature point pairs are extracted, their preference vectors are generated in similar conceptual space. By introducing the shared nearest neighbour in clustering procedure, the feature point pairs with smaller Jaccard distance and more shared nearest neighbours simultaneously are clustered into the same planar region. Because the relationship between the feature point pairs is considered, the accuracy of the inlier probability is high. Our method can detect multi-planar regions correctly without pre-determining the number of regions, and the corresponding clustered feature point pairs can be easily utilised for image mosaic. The experimental results show the effectiveness of the proposed method.     

一类广义Petersen图的(2,1)-全标号

图G=(V,E)的一个k-(2,1)-全标号定义为从集合V(G)∪E(G)到{0,1,2,…,k}的映射,使得任意两个相邻的点和相邻的边得到不同的标号,且任一对相关联的点和边得到的标号的差绝对值至少为2.G的(2,1)-全标号数是G的所有k-(2,1)-全标号中的最小的k值.得到了一类广义Petersen图的(2,1)-全标号数.     

完全图的剖分图的线图的谱

如果一个图G的邻接矩阵A(G)的特征多项式的所有特征值全为整数,则称图G是整的.设图L2(Kp):L(s(Kp))是完全图Kp的剖分图S(Kp)的线图.在这篇文章里,我们利用图的理论给出了S(Kp)和L2(Kp)的特征多项式及其谱.对于图L2(Kp),得到了其补图、线图、线图的补图及补图的线图的特征多项式.也证明了这些图都是整图.这些整图的发现是对整图的研究的一个新贡献.     

Gearing optimization

We consider an optimization problem that arises in machine-tool design. It deals with optimization of the structure of gearbox, which is normally represented by a graph. The edges of such a graph correspond to pairs of gear-wheels and the vertices stand for velocities. There is a designated input vertex and a set of output vertices. The problem is to create a graph with given number of output vertices while minimizing the total number of vertices. We present an integer programming formulation of this problem and propose an efficient solution in the special case of regular graphs. The author gratefully acknowledges the support of DIMAP—the Center for Discrete Mathematics and its Applications at the University of Warwick.     

Graph algebras and the graph isomorphism problem

We consider the families of matrix algebras over C associated with graphs. Restricting the multiplicity of the irreducible representations over C produces corresponding classes of graphs. The main result of the paper is a polynomial-time algorithm for recognizing the isomorphism of graphs from these classes. It is a generalization of the well-known Babai-Grigor'ev-Mount algorithm for testing the isomorphism of graphs with bounded eigenvalue multiplicity.     

Vertex Cover Optimization Using a Novel Graph Decomposition Approach

The minimum vertex cover problem (MVCP) is a well-known combinatorial optimization problem of graph theory. The MVCP is an NP (nondeterministic polynomial) complete problem and it has an exponential growing complexity with respect to the size of a graph. No algorithm exits till date that can exactly solve the problem in a deterministic polynomial time scale. However, several algorithms are proposed that solve the problem approximately in a short polynomial time scale. Such algorithms are useful for large size graphs, for which exact solution of MVCP is impossible with current computational resources. The MVCP has a wide range of applications in the fields like bioinformatics, biochemistry, circuit design, electrical engineering, data aggregation, networking, internet traffic monitoring, pattern recognition, marketing and franchising etc. This work aims to solve the MVCP approximately by a novel graph decomposition approach. The decomposition of the graph yields a subgraph that contains edges shared by triangular edge structures. A subgraph is covered to yield a subgraph that forms one or more Hamiltonian cycles or paths. In order to reduce complexity of the algorithm a new strategy is also proposed. The reduction strategy can be used for any algorithm solving MVCP. Based on the graph decomposition and the reduction strategy, two algorithms are formulated to approximately solve the MVCP. These algorithms are tested using well known standard benchmark graphs. The key feature of the results is a good approximate error ratio and improvement in optimum vertex cover values for few graphs.     

A new approach to the block layout problem

The main problem concerned with applying graph theory to facilities layout is the conversion of the dual graph to a block layout. This paper presents a new method of producing a planar orthogonal layout or floorplan of a set of facilities subject to adjacency and area constraints. It improves upon previous approaches by accepting any maximal planar graph representing the adjacencies as input. Simple selection criteria for choosing the next facility to be inserted into the floorplan are used. Further, any sensible orthogonal shape for the facilities in the resulting floorplan can be generated.     

基于环分布的频繁子图挖掘算法

频繁了图挖掘主要涉及到子图搜索和子图同构问题.对子图搜索问题,本文提出了环分布的概念,并构造了基于环分布的子图搜索算法:对了图同构问题,本文利用度序列和特征值构造了两种算法,分别用于对有向图和无向图的同构判别.利用同构算法对搜索出的子图进行同构分类,根据分类结果得到频繁了图.实验结果表明,本算法的效率优于现有算法.     

Automated generation and analysis of dynamic system designs

This research uses Genetic Algorithms (GA) to suggest new dynamic systems based on topological remapping of system constituents. The bondgraph representation of the dynamic system behavior is evolved by the operators encapsulated in the genetic algorithms to meet the specified design criteria. The resultant evolved graph is assembled by designers with schemes to produce design variants. Behavioral transformation and structural transformation are adopted as strategies to generate design variants that extend beyond the scope of parametric design into innovative design. Behavioral transformation involves changes in the structure of the representation graphs, while maintaining the functions. Structural transformation involves changes in the components and the subsystems represented by the graph fragments. GAs are used to implement the operators of the transformation to search the problem-solution space because GAs are very robust search routines. Further, since the goal is to generate many solutions, genetic speciation is used to diverge the search so as to uncover other desirable solutions. The dynamic systems are modeled using bond graphs. Bond graphs provide a unified approach to the analysis, synthesis and evaluation of dynamic engineering systems. Though the scope of this investigation is limited to systems represented by bond graphs, the domain is wide enough to include many interesting applications like pump systems and vibration isolation systems.     

Topological characterization of the Ge-Sb-Te phase diagram

Topological images of the Ge-Sb-Te phase diagram are constructed on the basis of two versions of the phase relations between the low-temperature forms of Ge_1-δTe in the Ge-Te system. The images have the form of flow diagrams and graphs, with labeled nodes representing the phases existing in the system. The graph edges represent two-phase mixtures and are labeled by the numbers of the phase reactions in which these mixtures appear and disappear. The graphs help to visualize the topology of the phase diagram in a compact form and are convenient for topological characterization and identification of phase reactions at invariant points.     

Co-authorship,rational Erdős numbers,and resistance distances in graphs

The Erdős number (EN) for collaborative papers among mathematicians was defined as indicating the topological distance in the graph depicting the co-authorship relations, i. e., EN = 1 for all co-authors of Paul Erdős; EN = 2 for their co-authors who did not publish jointly with Erdős; etc. A refinement of this notion uses resistance distances leading to rational Erdős numbers (REN), which (as indicated by their name) are rational numbers. For acyclic graphs, EN = REN, but for graphs with circuits these numbers differ. Further refinements are possible using weighted edges in the co-authorship graph according to the number of jointly authored papers. This revised version was published online in June 2006 with corrections to the Cover Date.     

关于图的边粘连度

图的边粘连度是反映网络脆弱程度的一个很好的参数．本文主要考察了极大或极小的非边粘连图的必要条件,给出了关于边粘连度的Nordhaus-Gaddum-type结果以及一些图运算下的边粘连度。     

顶点划分映射算法判定运动链同构

研究机构创新设计中运动链同构判定问题. 依据图论和机构拓扑学原理,提出子块、平方和度、子块关联度等概念;利用拓扑图顶点间连接关系,构造顶点分类集合;提出一种将所有顶点一一划分并两两映射的算法,实现同构识别. 实验结果证明该算法比现有算法效率高. 将算法设计基础理论应用于机构拓扑学,为该领域研究提供新思路