Search results for "Planar"
showing 10 items of 412 documents
Two graphs with a common edge
2014
Let G = G1 ∪ G2 be the sum of two simple graphs G1,G2 having a common edge or G = G1 ∪ e1 ∪ e2 ∪ G2 be the sum of two simple disjoint graphs G1,G2 connected by two edges e1 and e2 which form a cycle C4 inside G. We give a method of computing the determinant det A(G) of the adjacency matrix of G by reducing the calculation of the determinant to certain subgraphs of G1 and G2. To show the scope and effectiveness of our method we give some examples
An exact, complete and efficient implementation for computing planar maps of quadric intersection curves
2005
We present the first exact, complete and efficient implementation that computes for a given set P=p1,...,pn of quadric surfaces the planar map induced by all intersection curves p1∩ pi, 2 ≤ i ≤ n, running on the surface of p1. The vertices in this graph are the singular and x-extreme points of the curves as well as all intersection points of pairs of curves. Two vertices are connected by an edge if the underlying points are connected by a branch of one of the curves. Our work is based on and extends ideas developed in [20] and [9].Our implementation is complete in the sense that it can handle all kind of inputs including all degenerate ones where intersection curves have singularities or pa…
Dirichlet Forms, Poincaré Inequalities, and the Sobolev Spaces of Korevaar and Schoen
2004
We answer a question of Jost on the validity of Poincare inequalities for metric space-valued functions in a Dirichlet domain. We also investigate the relationship between Dirichlet domains and the Sobolev-type spaces introduced by Korevaar and Schoen.
Sobolev embeddings, extensions and measure density condition
2008
AbstractThere are two main results in the paper. In the first one, Theorem 1, we prove that if the Sobolev embedding theorem holds in Ω, in any of all the possible cases, then Ω satisfies the measure density condition. The second main result, Theorem 5, provides several characterizations of the Wm,p-extension domains for 1<p<∞. As a corollary we prove that the property of being a W1,p-extension domain, 1<p⩽∞, is invariant under bi-Lipschitz mappings, Theorem 8.
On Coloring Unit Disk Graphs
1998
In this paper the coloring problem for unit disk (UD) graphs is considered. UD graphs are the intersection graphs of equal-sized disks in the plane. Colorings of UD graphs arise in the study of channel assignment problems in broadcast networks. Improving on a result of Clark et al. [2] it is shown that the coloring problem for UD graphs remains NP-complete for any fixed number of colors k≥ 3 . Furthermore, a new 3-approximation algorithm for the problem is presented which is based on network flow and matching techniques.
Graphs of stable maps from closed surfaces to the projective plane
2018
Abstract We describe how to attach a weighted graph to each stable map from closed surfaces to projective plane and prove that any weighted graph with non negatively weighted vertices is the graph of some stable map from a closed surface to the projective plane.
Geometric Properties of Planar BV -Extension Domains
2009
We investigate geometric properties of those planar domains that are extension for functions with bounded variation.We start from a characterization of such domains given by Burago–Maz'ya and prove that a bounded, simply connected domain is a BV -extension domain if and only if its com- plement is quasiconvex. We further prove that the extension property is a bi-Lipschitz invariant and give applications to Sobolev extension domains.
On the continuity of discrete maximal operators in Sobolev spaces
2014
We investigate the continuity of discrete maximal operators in Sobolev space W 1;p (R n ). A counterexample is given as well as it is shown that the continuity follows under certain sucient assumptions. Especially, our research verifies that for the continuity in Sobolev spaces the role of the partition of the unity used in the construction of the maximal operator is very delicate.
Frequency Assignment and Multicoloring Powers of Square and Triangular Meshes
2005
The static frequency assignment problem on cellular networks can be abstracted as a multicoloring problem on a weighted graph, where each vertex of the graph is a base station in the network, and the weight associated with each vertex represents the number of calls to be served at the vertex. The edges of the graph model interference constraints for frequencies assigned to neighboring stations. In this paper, we first propose an algorithm to multicolor any weighted planar graph with at most $\frac{11}{4}W$ colors, where W denotes the weighted clique number. Next, we present a polynomial time approximation algorithm which garantees at most 2W colors for multicoloring a power square mesh. Fur…