Search

A set F of a graph is an edge dominating set if every edge in is adjacent to some edge in F. An edge domination number of G is the minimum cardinality of an edge dominating set. An edge dominating set F is called a doubly connected edge dominating set if the induced subgraphs and are connected. The minimum cardinality of the doubly connected edge dominating set in G is its domination number and is denoted by We study the graph theoretic properties of and its exact values for some standard graphs. The relation between with other parameters is also investigated.

This paper considers 1-string representations of planar graphs that are order-preserving in the sense that the order of crossings along the curve representing vertex v is the same as the order of edges in the clockwise order around v in the planar embedding. We show that this does not exist for all planar graphs (not even for all planar 3-trees), but show existence for some subclasses of planar partial 3-trees. In particular, for outer-planar graphs it can be order-preserving and outer-string in the sense that all ends of strings are on the outside of the representation.

A graph is k-planar \((k \ge 1)\) if it can be drawn in the plane such that no edge is crossed \(k+1\) times or more. A graph is k-quasi-planar \((k \ge 2)\) if it can be drawn in the plane with no k pairwise crossing edges. The families of k-planar and k-quasi-planar graphs have been widely studied in the literature, and several bounds have been proven on their edge density. Nonetheless, only trivial results are known about the relationship between these two graph families. In this paper we prove that, for \(k \ge 3\), every k-planar graph is \((k+1)\)-quasi-planar.

Three-dimensional 3D isothetic outer inner cover of a digital object is a 3D polytope of minimum maximum volume defined w.r.t. an underlying grid, having surfaces parallel to the coordinate planes, and circumscribing inscribing the entire object. It is useful for a unique approximation of 3D objects and to obtain shape-related information. We propose here a combinatorial algorithm for construction of such outer and inner covers of a 3D object imposed on the background grid. The algorithm consists of two passes. In the first pass, the unit faces on the surface of the cover are detected and stored in a doubly connected edge list DCEL. In the second pass, an efficient merging of contiguous and coplanar unit faces from the DCEL produces a compact representation of the cover. The accuracy of the cover can be adjusted by changing the face planes, whether placed uniformly or non-uniformly. Experimental results demonstrate the effectiveness of the algorithm.

We present an O(n) time algorithm for simultaneous embedding of pairs of planar graphs on the O(n2)× O(n2) grid, with at most three bends per edge, where n is the number of vertices. For the case when the input graphs are both trees, only one bend per edge is required. We also describe an O(n) time algorithm for simultaneous embedding with fixed-edges for tree-path pairs on the O(n)× O(n2) grid with at most one bend per tree-edge and no bends along path edges.

In this paper we extend the concept of the regular edge labeling for general plane graphs and for triconnected triangulated plane graphs to 4-connected triangulated plane graphs. We present two different linear time algorithms for constructing such a labeling. By using regular edge labeling, we present a new linear time algorithm for constructing rectangular dual of planar graphs. Our algorithm is simpler than previously known algorithms. The coordinates of the rectangular dual constructed by our algorithm are integers, while the one constructed by known algorithms are real numbers. Our second regular edge labeling algorithm is based on canonical ordering of 4-connected triangulated plane graphs. By using this technique, we present a new algorithm for constructing visibility representation of 4-connected planar graphs. Our algorithm reduces the size of the representation by a factor of 2 for such graphs.

We consider the problem of finding a planar embedding of a graph at fixed vertex locations that minimizes the total edge length. The problem is known to be NP-hard. We give polynomial time algorithms achieving an $O\sqrt{n} \log n$ approximation for paths and matchings, and an On approximation for general graphs.

We prove a theorem guaranteeing special paths of faces in 2-connected plane graphs. As a corollary, we obtain a new proof of Thomassen’s theorem that every 4-connected planar graph is Hamiltonian-connected.

A set P of points in R^2 is n-universal, if every planar graph on n vertices admits a plane straight-line embedding on P. Answering a question by Kobourov, we show that there is no n-universal point set of size n, for any n>=15. Conversely, we use a computer program to show that there exist universal point sets for all n, Fixed incorrect numbers of universal point sets in the last part

A combinatorial algorithm to find the intersection of an axis-parallel slicing plane with the orthogonal cover of a digital object is presented in this paper. The orthogonal cover is the smallest-volume 3D orthogonal polyhedron containing the object and stored in a doubly connected edge list (DCEL). Its intersection with the slicing plane consists of one or more isothetic polygons that provide topological information about the cover. The algorithm traverses the vertices on the polyhedron boundary and lying on the slicing plane, and the direction of next move from a vertex is determined by a set of linear equations in the integer domain. Results for few objects with successive slicing planes are presented to demonstrate the effectiveness and elegance of the algorithm.

An orthogonal point-set embedding of a planar graph G on a set S of points in Euclidean plane is a drawing of G where each vertex of G is placed on a point of S, each edge is drawn as a sequence of alternate horizontal and vertical line segments and any two edges do not cross except at their common end. In this paper, we devise an algorithm for orthogonal point-set embedding of 3-connected cubic planar graphs having a hamiltonian cycle with at most (5n over 2 + 2) bends, where n is the number of vertices in G. We also give an algorithm for finding an orthogonal point-set embedding of 4-connected planar graphs with at most 6n bends. Both the algorithms run in linear time. To the best of our knowledge this is the first work on orthogonal point-set embeddings with fewer bends.

In this paper we introduce cyclic level planar graphs, which are a planar version of the recurrent hierarchies from Sugiyama et al. and the cyclic extension of level planar graphs, where the first level is the successor of the last level. We study the testing and embedding problem and solve it for strongly connected graphs in time O(|V| log |V|).

International audience; Given a family of k disjoint connected polygonal sites in general position and of total complexity n, we consider the farthest-site Voronoi diagram of these sites, where the distance to a site is the distance to a closest point on it. We show that the complexity of this diagram is O(n), and give an O(n log^3 n) time algorithm to compute it. We also prove a number of structural properties of this diagram. In particular, a Voronoi region may consist of k-1 connected components, but if one component is bounded, then it is equal to the entire region.

The family of well-orderly maps is a family of planar maps with the property that every connected planar graph has at least one plane embedding which is a well-orderly map. We show that the number of well-orderly maps with n nodes is at most 2 αn + O (log n ), where α≈4.91. A direct consequence of this is a new upper bound on the number p(n) of unlabeled planar graphs with n nodes, log2p(n)≤4.91n. The result is then used to show that asymptotically almost all (labeled or unlabeled), (connected or not) planar graphs with n nodes have between 1.85n and 2.44n edges. Finally we obtain as an outcome of our combinatorial analysis an explicit linear-time encoding algorithm for unlabeled planar graphs using, in the worst-case, a rate of 4.91 bits per node and of 2.82 bits per edge.

An approach for computing a hierarchical approximation of planar Voronoi diagrams for different site shapes (points, line-segments, curve-arc segments, ...) and different distance functions (Euclidean metrics, convex distance functions, ...) was presented in [3]. The approach is based on the Voronoi-Quadtree, a quadtree data structure from which a polygonal approximation, represented by a DCEL structure, of the associated Voronoi region boundaries can be computed at different levels of detail. In this paper we describe efficient algorithms for dynamically maintaining, under the insertion or deletion of sites, the Voronoi-Quadtree and the corresponding DCEL structure representing an approximation of a Generalized Voronoi diagram.

We present a new general 3-color criterion for planar graphs. Applying this criterion we characterize a broad class of 3-colorable planar graphs and provide a corresponding linear time 3-coloring algorithm. We also characterize fully infinite 3-colorable planar triangulations.

The existing literature gives efficient algorithms for mapping trees or less restrictively outerplanar graphs on a given set of points in a plane, so that the edges are drawn planar and as straight lines. We relax the latter requirement and allow very few bends on each edge while considering general plane graphs. Our results show two algorithms for mapping four-connected plane graphs with at most one bend per edge and for mapping general plane graphs with at most two bends per edge. Furthermore we give a point set, where for arbitrary plane graphs it is NP-complete to decide whether there is an mapping such that each edge has at most one bend.

Planar st -graphs find applications in a number of areas. In this paper we present efficient parallel algorithms for solving several fundamental problems on planar st -graphs. The problems we consider include all-pairs shortest paths in weighted planar st -graphs, single-source shortest paths in weighted planar layered digraphs (which can be reduced to single-source shortest paths in certain special planar st -graphs), and depth-first search in planar st -graphs. Our parallel shortest path techniques exploit the specific geometric and graphic structures of planar st -graphs, and involve schemes for partitioning planar st -graphs into subgraphs in a way that ensures that the resulting path length matrices have a monotonicity property [1], [2]. The parallel algorithms we obtain are a considerable improvement over the previously best known solutions (when they are applied to these st -graph problems), and are in fact relatively simple. The parallel computational models we use are the CREW PRAM and EREW PRAM.

Let G be a planar graph of n vertices, v1,..., vn, and let {p1,...,pn} be a set of n points in the plane. We present an algorithm for constructing in O(n2) time a planar embedding of G, where vertex vi is represented by point pi and each edge is represented by a polygonal curve with O(n) bends (internal vertices.) This bound is asymptotically optimal in the worst case. In fact, if G is a planar graph containing at least m pairwise independent edges and the vertices of G are randomly assigned to points in convex position, then, almost surely, every planar embedding of G mapping vertices to their assigned points and edges to polygonal curves has at least m/20 edges represented by curves with at least m/403 bends.

The object of this paper is to show that 4-connected planar graphs are uniquely determined from their collection of edge-deleted subgraphs.

Every graph appearing in this note is a finite edge graph without loops and multiple edges. Denote by G(n, m) a graph with n vertices and ni edges . K r (t) denotes a graph with r groups of t vertices each, in which two vertices are connected if and only if they belong to different groups . By dividing n vertices into r-1 almost equal groups and connecting the points in different groups one obtains a graph on n vertices with ((r 2)/2(r 1) + u (1)) 11 2 edges which does not contain a Kr(l) . On the other hand, it was shown by Erdős and Stone [7] that ((r 2)/2(r 1) + s) n2 (e > 0) edges assure already the existence of a Kr(t), where t -~ oo as n -p co . This result is the inost essential part of the theorems on the structure of extremal graphs, see e .g. [3], [4], [6], [9] . Let us formulate the result of Erdős and Stone more precisely . Given n, r and e, put rn = [((r-2)/2(r-1)+e)n2] ([x] denotes the integer part of x) and define g(n, r, e) = min {t : every G(n, in) contains a K r (t)} .

A graph G is randomly planar if every planar embedding of every connected subgraph of G can be extended to a planar embedding of G. We classify these graphs.

11th International Symposium, WADS 2009, Banff, Canada, August 21-23, 2009. Proceedings, We study the problem of reconfiguring one list edge-coloring of a graph into another list edge-coloring by changing one edge color at a time, while at all times maintaining a list edge-coloring, given a list of allowed colors for each edge. First we show that this problem is PSPACE-complete, even for planar graphs of maximum degree 3 and just six colors. Then we consider the problem restricted to trees. We show that any list edge-coloring can be transformed into any other under the sufficient condition that the number of allowed colors for each edge is strictly larger than the degrees of both its endpoints. This sufficient condition is best possible in some sense. Our proof yields a polynomial-time algorithm that finds a transformation between two given list edge-colorings of a tree with n vertices using O(n [superscript 2]) recolor steps. This worst-case bound is tight: we give an infinite family of instances on paths that satisfy our sufficient condition and whose reconfiguration requires Ω(n [superscript 2]) recolor steps.