701
Common-Face Embeddings of Planar Graphs
Given a planar graph $\Ggg$ and a sequence ${\CC}_1,\ldots,{\CC}_q$, where each ${\CC}_i$ is a family of vertex subsets of $\Ggg$, we wish to find a plane embedding of $\Ggg$, if any exists, such that, for each $i\in\{1,\ldots,q\}$, there is a face Fi in the embedding whose boundary contains at least one vertex from each set in CCi. This problem has applications in the recovery of topological information from geographical data and the design of constrained layouts in VLSI. Let $\inputsize$ be the input size, i.e., the total number of vertices and edges in $\Ggg$ and the families CCi, counting multiplicity. We show that this problem is NP-complete in general. We also show that it is solvable in $O(\inputsize\log \inputsize)$ time for the special case in which, for each input family CCi, each set in CCi induces a connected subgraph of the input graph $\Ggg$. Note that the classical problem of simply finding a planar embedding is a further special case of this case with q=0. Therefore, the processing of the additional constraints CC1, . . .,CCq incurs only a logarithmic factor of overhead.
38006851
Approximation Algorithms for Independent Sets in Map Graphs
This paper presents polynomial-time approximation algorithms for the problem of computing a maximum independent set in a given map graph G with or without weights on its vertices. If G is given together with a map, then a ratio of 1+δ can be achieved in O(n2) time for any given constant δ > 0, no matter whether each vertex of G is given a weight or not. In case G is given without a map, a ratio of 4 can be achieved in O(n7) time if no vertex is given a weight, while a ratio of O(log n) can be achieved in O(n7 log n) time otherwise. Behind the design of our algorithms are several fundamental results for map graphs; these results can be used to design good approximation algorithms for coloring and vertex cover in map graphs, and may find applications to other problems on map graphs as well.
20004613
Disk Embeddings of Planar Graphs
Abstract 
Given a planar graph $G=(V,E)$ and a rooted forest ${\FF}=(V_{\FF}, A_{\FF})$ 
with leaf set $V$, we wish to decide whether $G$ has a plane embedding $\GG$ 
satisfying the following condition: There are $|V_{\FF}|-|V|$ pairwise noncrossing 
Jordan curves in the plane one-to-one corresponding to the nonleaf vertices of 
${\FF}$ such that for every nonleaf vertex $f$ of ${\FF}$, the interior of the curve 
$\JJ_f$ corresponding to $f$ contains all the leaf descendants of $f$ in ${\FF}$
but contains no other leaves of ${\FF}$. 
This problem arises from theoretical studies in geographic database systems. 
It is unknown whether this problem can be solved in polynomial time. 
This paper presents an almost linear-time algorithm for a nontrivial special case 
where the set of leaf descendants of each nonleaf vertex $f$ in ${\FF}$ induces 
a connected subgraph of $G$. 


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.
5311208
Domain decomposition algorithms for mixed methods for second-order elliptic problems
Domain decomposition algorithms for mixed finite element methods for linear second-order elliptic problems in R 2 and R 3 are developed. A convergence theory for two-level and multilevel Schwarz methods applied to the algorithms under consideration is given. It is shown that the condition number of these iterative methods is bounded uniformly from above in the same manner as in the theory of domain decomposition methods for conforming and nonconforming finite element methods for the same differential problems. Numerical experiments are presented to illustrate the present techniques.
2801577
Scalable collaborative filtering using cluster-based smoothing
Memory-based approaches for collaborative filtering identify the similarity between two users by comparing their ratings on a set of items. In the past, the memory-based approach has been shown to suffer from two fundamental problems: data sparsity and difficulty in scalability. Alternatively, the model-based approach has been proposed to alleviate these problems, but this approach tends to limit the range of users. In this paper, we present a novel approach that combines the advantages of these two approaches by introducing a smoothing-based method. In our approach, clusters generated from the training data provide the basis for data smoothing and neighborhood selection. As a result, we provide higher accuracy as well as increased efficiency in recommendations. Empirical studies on two datasets (EachMovie and MovieLens) show that our new proposed approach consistently outperforms other state-of-art collaborative filtering algorithms.
1865477
On integral sum graphs
A graph G is said to be an integral sum graph if its nodes can be given a labeling f with distinct integers, so that for any two distinct nodes u and v of G, uv is an edge of G if and only if f(u)+f(v)=f(w) for some node w in G. A node of G is called a saturated node if it is adjacent to every other node of G. We show that any integral sum graph which is not K"3 has at most two saturated nodes. We determine the structure for all integral sum graphs with exactly two saturated nodes, and give an upper bound for the number of edges of a connected integral sum graph with no saturated nodes. We introduce a method of identification on constructing new connected integral sum graphs from given integral sum graphs with a saturated node. Moreover, we show that every graph is an induced subgraph of a connected integral sum graph. Miscellaneous related results are also presented.
28595321
A PTAS for a Disc Covering Problem Using Width-Bounded Separators
In this paper, we study the following disc covering problem: Given a set of discs of various radii on the plane, find a subset of discs to maximize the area covered by exactly one disc. This problem originates from the application in digital halftoning, with the best known approximation factor being 5.83 [2]. We show that if the maximum radius is no more than a constant times the minimum radius, then there exists a polynomial time approximation scheme. Our techniques are based on the width-bounded geometric separator recently developed in [5,6].
1777247
Web-page classification through summarization
Web-page classification is much more difficult than pure-text classification due to a large variety of noisy information embedded in Web pages. In this paper, we propose a new Web-page classification algorithm based on Web summarization for improving the accuracy. We first give empirical evidence that ideal Web-page summaries generated by human editors can indeed improve the performance of Web-page classification algorithms. We then propose a new Web summarization-based classification algorithm and evaluate it along with several other state-of-the-art text summarization algorithms on the LookSmart Web directory. Experimental results show that our proposed summarization-based classification algorithm achieves an approximately 8.8% improvement as compared to pure-text-based classification algorithm. We further introduce an ensemble classifier using the improved summarization algorithm and show that it achieves about 12.9% improvement over pure-text based methods.