共查询到20条相似文献,搜索用时 31 毫秒
1.
A star-shaped drawing of a graph is a straight-line drawing such that each inner facial cycle is drawn as a star-shaped polygon, and the outer facial cycle is drawn as a convex polygon. In this paper, we consider the problem of finding a star-shaped drawing of a biconnected planar graph with the minimum number of concave corners. We first show new structural properties of planar graphs to derive a lower bound on the number of concave corners. Based on the lower bound, we prove that the problem can be solved in linear time by presenting a linear-time algorithm for finding a best plane embedding of a biconnected planar graph with the minimum number of concave corners. This is in spite of the fact that a biconnected planar graph may have an exponential number of different plane embeddings. 相似文献
2.
Symmetry is one of the most important aesthetic criteria in graph
drawing because it reveals the structure in the graph. This paper
discusses symmetric drawings of biconnected planar graphs. More
specifically, we discuss geometric automorphisms, that is,
automorphisms of a graph G that can be represented as symmetries
of a drawing of G. Finding geometric automorphisms is the first
and most difficult step in constructing symmetric drawings of
graphs. The problem of determining whether a given graph has a
non-trivial geometric automorphism is NP-complete for general
graphs. In this paper we present a linear time algorithm for
finding planar geometric automorphisms of biconnected planar
graphs. A drawing algorithm is also discussed. 相似文献
3.
Symmetry is one of the most important aesthetic criteria in graph
drawing because it reveals structure in the graph. This paper
discusses symmetric drawings of oneconnected planar graphs.
More specifically, we discuss planar (geometric)
automorphisms, that is, automorphisms of a graph G that can be
represented as symmetries of a planar drawing of G. Finding
planar automorphisms is the first and most difficult step in
constructing planar symmetric drawings of graphs. The problem of
determining whether a given graph has a nontrivial geometric
automorphism is NP-complete for general graphs. The two previous papers in this series have discussed the problem
of drawing planar graphs with a maximum number of symmetries, for
the restricted cases where the graph is triconnected and
biconnected. This paper extends the previous results to cover
planar graphs that are oneconnected. We present a linear
time algorithm for drawing oneconnected planar graphs with a
maximum number of symmetries. 相似文献
4.
《Computers & chemistry》1994,18(2):189-193
An algorithm for coding of chemical structures is proposed based on a chemistry oriented line notation language. The latter is based on simple rules providing an almost convention free specification of molecular connectivity. A very useful feature of the proposed molecular code is that it has a line notation form, i.e. it can be interpreted according to the line notation language rules. Both the line notation language and molecular code are based on the principle of decomposition of the molecular graph into biconnected components (cyclic fragments or single atoms). The decomposition graph is a tree, each vertex of which stands for a biconnected component. Within the coding algorithm first the codes for each biconnected component are formed and then they are used as vertex labels of the decomposition tree. Since large chemical graphs usually consist of several biconnected components this method improves, to a great extent, the average time complexity of the algorithm. Terminal cyclic radicals and chain fragments of the molecular graph appear as unique substrings in the line notation code which enhances their computer perception. 相似文献
5.
We present a new algorithm for drawing planar graphs on the plane. It can be viewed as a generalization of the algorithm
of Chrobak and Payne, which, in turn, is based on an algorithm by de Fraysseix, Pach, and Pollack. Our algorithm improves
the previous ones in that it does not require a preliminary triangulation step; triangulation proves problematic in drawing
graphs ``nicely,' as it has the tendency to ruin the structure of the input graph. The new algorithm retains the positive
features of the previous algorithms: it embeds a biconnected graph of n vertices on a grid of size (2n-4) x (n-2) in linear time. We have implemented the algorithm as part of a software system for drawing graphs nicely.
Received September 21, 1995; revised March 15, 1996. 相似文献
6.
McCreary C.L. Chapman R.O. Shieh F.-S. 《IEEE transactions on systems, man, and cybernetics. Part A, Systems and humans : a publication of the IEEE Systems, Man, and Cybernetics Society》1998,28(5):545-561
This paper presents a procedure for automatically drawing directed graphs. Our system, Clan-based Graph Drawing Tool (CG), uses a unique clan-based graph decomposition to determine intrinsic substructures (clans) in the graph and to produce a parse tree. The tree is given attributes that specify the node layout. CG then uses tree properties with the addition of “routing nodes” to route the edges. The objective of the system is to provide, automatically, an aesthetically pleasing visual layout for arbitrary directed graphs. The prototype has shown the strengths of this approach. The innovative strategy of clan-based graph decomposition is the first digraph drawing technique to analyze locality in the graph in two dimensions. The typical approach to drawing digraphs uses a single dimension, level, to arrange the nodes 相似文献
7.
《国际计算机数学杂志》2012,89(14):3138-3148
Most of graph drawing algorithms draw graphs on unbounded planes. However, there are applications that require graphs to be drawn on the plane inside a given polygon. In this paper, a new algorithm for planar orthogonal drawing of complete binary trees inside rectilinear polygons is presented. Uniform distribution of nodes of graphs on drawing regions is one of the aesthetics criteria in graph drawing. The goal of this paper is to produce planar orthogonal drawings with a relatively uniform node distribution and few edge bends. The proposed algorithm can be considered as a generalization of the H-tree layout method for rectilinear polygons. A new linear time algorithm is also given for bisecting rectilinear polygons into two equi-area rectilinear sub-polygons. 相似文献
8.
Visualizing graphs has been studied extensively in the community of graph drawing and information visualization over the years. In some applications, the user is required to interact with a graph by making slight changes to the underlying graph structure. To visualize graphs in such an interactive environment, it is desirable that the differences between the displays of the original and the modified graphs be kept minimal, allowing the user to comprehend the changes in the graph structure faster. As the mental map concept refers to the presentation of a person’s mind while exploring visual information, the better the mental map is preserved, the easier the structure change of a graph is understood. It is somewhat surprising that preserving the user’s mental map has largely been ignored in the graph drawing community in the past. We propose an effective mental-map-preserving graph drawing algorithm for straight-line drawings of general undirected graphs based on the simulated-annealing technique. Our experimental results and questionnaire analysis suggest this new approach to be promising. 相似文献
9.
Triangulation of planar graphs under constraints is a fundamental problem in the representation of objects. Related keywords
are graph augmentation from the field of graph algorithms and mesh generation from the field of computational geometry. We
consider the triangulation problem for planar graphs under the constraint to satisfy 4-connectivity. A 4-connected planar
graph has no separating triangles, i.e., cycles of length 3 which are not a face.
We show that triangulating embedded planar graphs without introducing new separating triangles can be solved in linear time
and space. If the initial graph had no separating triangle, the resulting triangulation is 4-connected. If the planar graph
is not embedded, then deciding whether there exists an embedding with at most k separating triangles is NP-complete. For biconnected graphs a linear-time approximation which produces an embedding with
at most twice the optimal number is presented. With this algorithm we can check in linear time whether a biconnected planar
graph can be made 4-connected while maintaining planarity. Several related remarks and results are included.
Received August 1, 1995; revised July 8, 1996, and August 23, 1996. 相似文献
10.
提出了一种基于遗传算法的新的平面图平面正交直线画图算法,算法将平面图画图问题转化为约束优化问题,根据画图问题选定的美观准则构造约束函数,用遗传算法求解目标函数的最优解的近似值,从而得到平面图的平面正交直线画法。新算法的优点是方法简单,易于实现,画出的图形美观,算法稳定性好。实验结果表明,画图算法的最终结果不依赖于图的初始状态。 相似文献
11.
Citation graphs representing a body of scientific literature convey measures of scholarly activity and productivity. In this work we present a study of the structure of the citation graph of the computer science literature. Using a web robot we built several topic-specific citation graphs and their union graph from the digital library ResearchIndex. After verifying that the degree distributions follow a power law, we applied a series of graph theoretical algorithms to elicit an aggregate picture of the citation graph in terms of its connectivity. We discovered the existence of a single large weakly-connected and a single large biconnected component, and confirmed the expected lack of a large strongly-connected component. The large components remained even after removing the strongest authority nodes or the strongest hub nodes, indicating that such tight connectivity is widespread and does not depend on a small subset of important nodes. Finally, minimum cuts between authority papers of different areas did not result in a balanced partitioning of the graph into areas, pointing to the need for more sophisticated algorithms for clustering the graph. 相似文献
12.
Jänicke S Heine C Hellmuth M Stadler PF Scheuermann G 《IEEE transactions on visualization and computer graphics》2010,16(6):1082-1089
Graphs are a versatile structure and abstraction for binary relationships between objects. To gain insight into such relationships, their corresponding graph can be visualized. In the past, many classes of graphs have been defined, e.g. trees, planar graphs, directed acyclic graphs, and visualization algorithms were proposed for these classes. Although many graphs may only be classified as "general" graphs, they can contain substructures that belong to a certain class. Archambault proposed the TopoLayout framework: rather than draw any arbitrary graph using one method, split the graph into components that are homogeneous with respect to one graph class and then draw each component with an algorithm best suited for this class. Graph products constitute a class that arises frequently in graph theory, but for which no visualization algorithm has been proposed until now. In this paper, we present an algorithm for drawing graph products and the aesthetic criterion graph product's drawings are subject to. We show that the popular High-Dimensional Embedder approach applied to cartesian products already respects this aestetic criterion, but has disadvantages. We also present how our method is integrated as a new component into the TopoLayout framework. Our implementation is used for further research of graph products in a biological context. 相似文献
13.
Evaluating esthetics for user-sketched layouts of clustered graphs with known clustering information
This paper aims to empirically analyze the esthetics for user-sketched layouts of clustered graphs with known clustering information. In our experiments, given not only the adjacency list of a clustered graph but also its predefined clustering information, each participant was asked to manually sketch clustered graphs “nicely” from scratch on a tablet system using a stylus. Different from previous works, the main concern in this paper is on which graph drawing esthetics people favor when sketching their own drawings of clustered graphs with known clustering information. Another concern of this paper is on the esthetics of clustered graph layouts employed by participants which include not only characteristics and structures of the final graph layouts but also the behavior of user's sketching process (including layout creation and adjustment). By observing all layouts and drawing processes, the drawing strategies which participants applied and the drawing esthetics are analyzed. Results show that most participants were unsurprisingly able to draw graphs with clear presence of bridge edges and clustering cohesiveness; more importantly, to distinguish clusters within the restricted-size tablet screen during the drawing process, some of the participants were still able to make each cluster with fewer edge crossings, more symmetries, and more alignment of grid in a smaller drawing area where the cluster spreads. Our results support that to alleviate user's complex drawing tasks, aside from the grid-based editing function suggested by the previous work, graph drawing systems should also provide the clustering information if the structure of the graph to be drawn is known. 相似文献
14.
A new approach to the problem of graph and subgraph isomorphism detection from an input graph to a database of model graphs is proposed in this paper. It is based on a preprocessing step in which the model graphs are used to create a decision tree. At run time, subgraph isomorphisms are detected by means of decision tree traversal. If we neglect the time needed for preprocessing, the computational complexity of the new graph algorithm is only polynomial in the number of input graph vertices. In particular, it is independent of the number of model graphs and the number of edges in any of the graphs. However, the decision tree is of exponential size. Several pruning techniques which aim at reducing the size of the decision tree are presented. A computational complexity analysis of the new method is given and its behavior is studied in a number of practical experiments with randomly generated graphs. 相似文献
15.
Hierarchical graphs and clustered graphs are useful non-classical graph models for structured relational information. Hierarchical graphs are graphs with layering structures; clustered graphs are graphs with recursive clustering structures. Both have applications in CASE tools, software visualization and VLSI design. Drawing algorithms for hierarchical graphs have been well investigated. However, the problem of planar straight-line representation has not been solved completely. In this paper we answer the question: does every planar hierarchical graph admit a planar straight-line hierarchical drawing? We present an algorithm that constructs such drawings in linear time. Also, we answer a basic question for clustered graphs, that is, does every planar clustered graph admit a planar straight-line drawing with clusters drawn as convex polygons? We provide a method for such drawings based on our algorithm for hierarchical graphs. 相似文献
16.
17.
Complete characterizations are given for those trees that can be drawn as either the relative neighborhood graph, relatively closest graph, Gabriel graph, or modified Gabriel graph of a set of points in the plane. The characterizations give rise to linear-time algorithms for determining whether a tree has such a drawing; if such a drawing exists one can be constructed in linear time in the real RAM model. The characterization of Gabriel graphs settles several conjectures of Matula and Sokal [17].This research was conducted while the author was at the School of Computer Science of McGill University. Research supported in part by NSERC and FCAR.This work was done when this author was visiting the School of Computer Science of McGill University.This work was done when this author was visiting the School of Computer Science of McGill University. 相似文献
18.
Output-Sensitive Reporting of Disjoint Paths 总被引:1,自引:0,他引:1
A k -path query on a graph consists of computing k vertex-disjoint paths between two given vertices of the graph, whenever they exist. In this paper we study the problem of
performing k -path queries, with , in a graph G with n vertices. We denote with the total length of the reported paths. For , we present an optimal data structure for G that uses O(n) space and executes k -path queries in output-sensitive time. For triconnected planar graphs, our results make use of a new combinatorial structure that plays the same role as
bipolar (st ) orientations for biconnected planar graphs. This combinatorial structure also yields an alternative construction of convex
grid drawings of triconnected planar graphs.
Received August 24, 1996; revised April 8, 1997. 相似文献
19.
The transitive closure problem in O (1) time is solved by a new method that is far different from the conventional solution method. On processor arrays with reconfigurable bus systems, two O (1) time algorithms are proposed for computing the transitive closure of an undirected graph. One is designed on a three-dimensional n ×n ×n processor array with a reconfigurable bus system, and the other is designed on a two-dimensional n 2×n 2 processor array with a reconfigurable bus system, where n is the number of vertices in the graph. Using the O (1) time transitive closure algorithms, many other graph problems are solved in O (1) time. These problems include recognizing bipartite graphs and finding connected components, articulation points, biconnected components, bridges, and minimum spanning trees in undirected graphs 相似文献
20.
A hierarchy tree of a graph G is a rooted tree whose leaves are the
vertices of G; the internal nodes are usually called clusters.
Hierarchy trees are well suited for representing hierarchical
decompositions of graphs. In this paper we introduce the notion of
P-validity of hierarchy trees with respect to a given graph property P. This notion reflects the similarity between any high-level
representation of G obtained from the hierarchy tree and the
topological structure of G. Maintaining the properties of a graph
at any level of abstraction is especially relevant in graph drawing
applications. We present a structural characterization of P-valid
hierarchy trees when the clustered graph is a tree and property P is the acyclicity. Besides being interesting in its own
right, our
structure theorem can be used in the design of a polynomial time
algorithm for recognizing P-valid hierarchy trees. 相似文献