40482210
Grid Embedding of 4-Connected Plane Graphs
A straight line grid embedding of a plane graph G is a drawing of G such that the vertices are drawn at grid points and the edges are drawn as non-intersecting straight line segments. In this paper, we show that, if a 4-connected plane graph G has at least 4 vertices on its exterior face, then G can be embedded on a grid of size W×H such that W+H≤n, W≤(n+3)/2 and H≤2(n−1)/3, where n is the number of vertices of G. Such an embedding can be computed in linear time.
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].
15559790
Improved visibility representation of plane graphs
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 [Discrete Comput. Geom. 1 (1986) 343-353] and Tamassia and Tollis [Discrete Comput. Geom. 1 (1986) 321-341] independently gave linear time VR algorithms for 2-connected plane graph. Using this approach, the height of the VR is bounded by (n - 1), the width is bounded by (2n - 5). After that, some work has been done to find a more compact VR. Kant and He [Theoret. Comput. Sci. 172 (1997) 175-193] proved that a 4-connected plane graph has a VR with width bounded by (n - 1). Kant [Internat. J. Comput. Geom. Appl. 7 (1997) 197-210] reduced the width bound to ⌊3n-6/2⌋ for general plane graphs. Recently, using a sophisticated greedy algorithm, Lin et al. reduced the width bound to ⌊22n-42/15⌋ [Proc. STACS'03, Lecture Notes in Computer Science, vol. 2607, Springer, Berlin, 2003, pp. 14-25].In this paper, we prove that any plane graph G has a VR with width at most ⌊13n-24/9⌋, which can be constructed by using the simple standard VR algorithm in [P. Rosenstiehl, R.E. Tarjan, Discrete Comput. Geom. 1 (1986) 343-353; R. Tamassia, I.G. Tollis, Discrete Comput. Geom. 1 (1986) 321-341].
25659954
An Improved Algorithm for the Planar 3-Cut Problem
Abstract A 3-cut of a connected graph G is a subset of edges which, when deleted, separates G into three connected components. In this paper we present an O ( n log n ) algorithm for finding a minimum 3-cut in planar graphs. Our algorithm improves the best previously known algorithm for the problem by an O( n log n) factor.
32419724
Grid Embedding of 4-Connected Plane Graphs
A straight line grid embedding of a plane graph G is a drawing of G such that the vertices are drawn at grid points and the edges are drawn as nonintersecting straight line segments. In this paper we show that if a 4-connected plane graph G has at least four vertices on its external face, then G can be embedded on a grid of size W × H such that W + H ≤n, W ≤ (n + 3)/2 and H ≤ 2(n - 1)/3, where n is the number of vertices of G. Such an embedding can be computed in linear time.
11889495
On Even Triangulations of 2-Connected Embedded Graphs
Recently, Hoffmann and Kriegel proved an important combinatorial theorem [SIAM J. Discrete Math., 9 (1996), pp. 210--224]: Every 2-connected bipartite plane multigraph G without 2-cycle faces has a triangulation in which all vertices have even degree (this is called an even triangulation). Combined with the classical Whitney's theorem, this result implies that every such graph has a 3-colorable plane triangulation. Using this theorem, Hoffmann and Kriegel significantly improved the upper bounds of several art gallery and prison guard problems. A complicated O(n2) time algorithm was obtained in [SIAM J. Discrete Math., 9 (1996), pp. 210--224] for constructing an even triangulation of G. Hoffmann and Kriegel conjectured that there is an O(n3/2) time algorithm for solving this problem. 
In this paper, we develop a simple proof of the above theorem. Our proof reveals and relies on a natural correspondence between even triangulations of G and certain orientations of G. Based on this new proof, we obtain a very simple O(n) time algorithm for finding an even triangulation of G. We also extend our proof to show the existence of even triangulations for similar graphs on high genus surface.
1711864
Automatically Generating Gene Summaries from Biomedical Literature
Biologists often need to find information about genes whose function is not described in the genome databases. Currently they must try to search disparate biomedical literature to locate relevant articles, and spend considerable efforts reading the retrieved articles in order to locate the most relevant knowledge about the gene. We describe our software, the first that automatically generates gene summaries from biomedical literature. We present a two-stage summarization method, which involves first retrieving relevant articles and then extracting the most informative sentences from the retrieved articles to generate a structured gene summary. The generated summary explicitly covers multiple aspects of a gene, such as the sequence information, mutant phenotypes, and molecular interaction with other genes. We propose several heuristic approaches to improve the accuracy in both stages. The proposed methods are evaluated using 10 randomly chosen genes from FlyBase and a subset of Medline abstracts about Drosophila. The results show that the precision of the top selected sentences in the 6 aspects is typically about 50-70%, and the generated summaries are quite informative, indicating that our approaches are effective in automatically summarizing literature information about genes. The generated summaries not only are directly useful to biologists but also serve as useful entry points to enable them to quickly digest the retrieved literature articles.
20452185
A methodology for test selection
Software creation requires not only testing during the development cycle by the development staff, but also independent testing following the completion of the implementation. However in the latter case, the amount of testing that can be carried out is often limited by time and resources. At the very most, independent testing can be expected to provide 100% test coverage of the test requirements (or specifications) associated with the software element with the minimum of effort. This paper describes a methodology employing integer programming by which the amount of testing required to provide the maximum possible test coverage of the test requirements (for the given test set) is assured while at the same time minimizing the total number of tests to be included in a test suite. A collateral procedure provides recommendations on which tests might be eliminated if less than 100% test coverage of the test requirements is permitted. This latter procedure will be useful in determining the risk of not running the minimum set of tests for 100% test coverage. A third process selects from the test matrix the set of tests to be applied to the system following maintenance modification of any test requirements-- that is, to provide a submatrix for regression testing. The potential benefits for applying the integer programming technique in test data selection is also discussed.
949912
Replicated Shared Object Model for Edge Detection with Spiral Architecture
Edge detection in computer vision and image processing is a process which detects one kind of significant features appearing as discontinuities in intensities. A parallel edge detection algorithm based on Spiral Architeture is designed in this paper by a Replicated Shared Object Model (RSOM). We use this approach to meet the need of replicated object management, update propagation, underlying communication and consistency maintenance among replicated objects.
41188840
Finding Double Euler Trails of Planar Graphs in Linear Time
This paper answers an open question in the design of complimentary metal-oxide semiconductor VLSI circuits. The question asks whether a polynomial-time algorithm can decide if a given planar graph has a plane embedding ${\cal E}$ such that ${\cal E}$ has an Euler trail P = e1 e2 ... em and its dual graph has an Euler trail $P^*=e^*_1 e^*_2 \ldots e^*_m$, where $e^*_i$ is the dual edge of ei for i=1,2,...,m. This paper answers this question in the affirmative by presenting a linear-time algorithm.
12494221
Statistical and computational analysis of locality preserving projection
Recently, several manifold learning algorithms have been proposed, such as ISOMAP (Tenenbaum et al., 2000), Locally Linear Embedding (Roweis & Saul, 2000), Laplacian Eigenmap (Belkin & Niyogi, 2001), Locality Preserving Projection (LPP) (He & Niyogi, 2003), etc. All of them aim at discovering the meaningful low dimensional structure of the data space. In this paper, we present a statistical analysis of the LPP algorithm. Different from Principal Component Analysis (PCA) which obtains a subspace spanned by the largest eigenvectors of the global covariance matrix, we show that LPP obtains a subspace spanned by the smallest eigenvectors of the local covariance matrix. We applied PCA and LPP to real world document clustering task. Experimental results show that the performance can be significantly improved in the subspace, and especially LPP works much better than PCA.