28695934
Alternating walks in partially 2-edge-colored graphs and optimal strength of graph labeling
Abstract A graph is partially 2-edge-colored if edges of G are colored by two colors, possibly with some edges uncolored. A walk is alternating in a partially 2-edge-colored graph if the given 2-edge-coloring can be extended to all edges of G such that colors alternate as the walk is traversed. We present a polynomial-time algorithm to decide, given a partially 2-edge-colored graph and two distinct vertices, whether there is an alternating walk connecting the two vertices. We apply the algorithm to solve problems in graph labeling. In particular, we show that the regularizable strength of a graph can be determined in polynomial time.
7862760
Tagged Probe Interval Graphs
A generalization of interval graph is introduced for cosmid contig mapping of DNA. A graph is a tagged probe interval graph if its vertex set can be partitioned into two subsets of probes and nonprobes, and a closed interval can be assigned to each vertex such that two vertices are adjacent if and only if at least one of them is a probe and one end of its corresponding interval is contained in the interval corresponding to the other vertex. We show that tagged probe interval graphs are weakly triangulated graphs, hence are perfect graphs. For a tagged probe interval graph with a given partition, we give a chordal completion that is consistent to any interval completions with respect to the same vertex partition.
33560656
Clique covering the edges of a locally cobipartite graph
Abstract We prove that a locally cobipartite graph on n vertices contains a family of at most n cliques that cover its edges. This is related to Opsut's conjecture that states the competition number of a locally cobipartite graph is at most two.
4374799
Appearance manifolds for modeling time-variant appearance of materials
We present a visual simulation technique called appearance manifolds for modeling the time-variant surface appearance of a material from data captured at a single instant in time. In modeling time-variant appearance, our method takes advantage of the key observation that concurrent variations in appearance over a surface represent different degrees of weathering. By reorganizing these various appearances in a manner that reveals their relative order with respect to weathering degree, our method infers spatial and temporal appearance properties of the material's weathering process that can be used to convincingly generate its weathered appearance at different points in time. Results with natural non-linear reflectance variations are demonstrated in applications such as visual simulation of weathering on 3D models, increasing and decreasing the weathering of real objects, and material transfer with weathering effects.
7877505
Three forbidden subgraphs for line graphs
We construct a set of three graphs with the property that a 3-connected graph with minimum degree at least 7 is a line graph if and only if it does not contain any of the three graphs as an induced subgraph. We also show that the number of excluded subgraphs cannot be reduced no matter what connectivity is specified.
44954899
Maximum Stabbing Line in 2D Plane
Two line estimator problems using the perpendicular and vertical distance measure are considered in this paper. (1) Given a set of n points in a plane, the line estimator problem is to determine a straight line which best fits this set of points. (2) Given a sequence of n points in a plane, the ordered line estimator problem is to determine a straight line which can best fit this set of points in order. Depending on the perpendicular/vertical distance measure, these two problems are related to the stabbing line problems of n circles/vertical line segments. With arrangement of curves, both problems can be solved in O(n2) and O(n3) time respectively.
1893362
Minimal Tetrahedralizations of a Class of Polyhedra
Given a simple polyhedron P in the three dimensional Euclidean space, different tetrahedralizations of P may contain different numbers of tetrahedra. The minimal tetrahedralization is a tetrahedralization with the minimum number of tetrahedra. In this paper, we present some properties of the graph of polyhedra. Then we identify a class of polyhedra and show that this kind of polyhedra can be minimally tetrahedralized in O(n2) time.
38065257
Tetrahedralization of Two Nested Convex Polyhedra
In this paper, we present an algorithm to tetrahedralize the region between two nested convex polyhedra without introducing Steiner points. The resulting tetrahedralization consists of linear number of tetrahedra. Thus, we answer the open problem raised by Chazelle and Shouraboura: "whether or not one can tetrahedralize the region between two nested convex polyhedra into linear number of tetrahedra, avoiding Steiner points?". Our algorithm runs in O((n+m)3 log(n+m)) time and produces 2(m+n-3) tetrahedra, where n and m are the numbers of the vertices in the two given polyhedra, respectively.