Search

There are many representations of planar graphs but few are as elegant as Turan’s (1984): it is simple and practical, uses only four bits per edge, can handle multi-edges and can store any specified embedding. Its main disadvantage has been that “it does not allow efficient searching” (Jacobson, 1989). In this paper we show how to add a sublinear number of bits to Turan’s representation such that it supports fast navigation, thus overcoming this disadvantage. Other data structures for planar embeddings may be asymptotically faster or smaller but ours is simpler, and that can be a theoretical as well as a practical advantage: e.g., we show how our structure can be built efficiently in parallel.

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.

In this paper, an efficient method for computing the cross-sections of the internal structure from a 3D human brain model has been proposed. It can extract image slices from the brain model in sagittal, coronal, and axial views used for computed tomography and ultrasonography. A doubly connected edge list (DCEL) has been used for speeding up the computation during geometric processing, since the DCEL captures the topological relationship among vertices, edges, and faces of the triangulated surface. For a sectional plane, image slices are computed quite efficiently using the information of geometric coherence from the previous sectional plane with the help of DCEL. The optimal distance between two successive sectional planes is determined from the frequency distribution (Poisson distribution) of the edge lengths in the model. It reduces computational overhead without compromising on the quality of output, as demonstrated by experimental results.

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.

The overlay algorithm is an important branch in computational geometry field, it is an important process for computing exact Minkowski sum of two convex polyhedrons. By improving the existing plane sweep algorithm, the overlay algorithm for simple subdivision of arbitrary polygon in plane is given. The algorithm can be used to overlay arbitrary polygon after subdivision into simple polygon in the plane. It has lower time complexity than the existing overlay algorithm. The whole algorithm consists of three steps: line segment intersection, reconstructing topology and constructing the DCEL for overlay graph. The results show that the algorithm can compute the overlay of two planar subdivisions in linear time.

The explicit construction of the conformal mapping of a concentric annulus to a doubly connected polygonal domain was first reported by Akhiezer in 1928. The construction of an analogous formula for the case of a polycircular arc domain, i.e. for a doubly connected domain whose boundaries are a union of circular arc segments, has remained an important open problem. In this paper, we present this explicit formula. We first introduce a new method for deriving the classical formula of Akhiezer and then show how to generalize the method to the case of a doubly connected polycircular arc domain. As an analytical check of the formula, a special exact solution for a doubly connected polycircular arc mapping is derived and compared with that obtained from the more general construction. As an illustrative example, a doubly connected polycircular arc domain arising in a classic potential flow problem considered in the last century by Lord Rayleigh is considered in detail.

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 novel algorithm is proposed to locate the sets of adjacent co-spherical triangles for a given object, which enables us to detect spheres and spherical parts constituting the object. An extension of the idea of Hough transform has been used, aided by axial discretization and restricted searching, along with the geometric data structure of doubly connected edge list. The algorithm has been analyzed and shown to achieve significant efficiency in space and run-time. On testing the algorithm with various 3D objects, it is found to produce the desired result. Effects of different input parameters have been explained and the robustness of the algorithm has been shown for rough/noisy surfaces.

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.

Planar graph routing works provably correct if the underlying network graph is connected and planar. Typically, wireless networks modeled as 2D graphs, are not planar and planar graph routing applied on such unprocessed network graphs may fail. Planarizing a given connected graph by removing intersecting links might be impossible if the outcome still needs to be a connected subgraph. It becomes even more difficult with distributed planarization techniques, where each node is allowed to use only the information about its local neighborhood. Furthermore, it is getting complicated if the nodes' assigned positions do not reflect the exact physical location. With or without exact location information, the outcome might be disconnected, nonplanar, or both of it. With all these unsolvable problems, the question arises how to apply planar graph routing in a realistic network setting? Fortunately, wireless network graphs bear one property which distinguishes them from arbitrary graphs: due to limited communication range, network links cannot become arbitrarily long. In this work we exploit this locality property to build a new localized planarization algorithm, which is location fault tolerant and which produces planar connected graphs in most cases in realistic wireless models. We evaluate our algorithm using the Log Normal Shadowing model and show that our algorithm always produces planar connected graphs in all simulations even when large location errors are present.

The orthogonal cover of a 3D digital object is a minimum-volume 3D polytope having surfaces parallel to the coordinate planes, and containing the entire object so as to capture its approximate shape information. An efficient algorithm for construction of such an orthogonal cover imposed on a background grid is presented in this paper. A combinatorial technique is used to classify the grid faces constituting the polytope while traversing along the surface of the object in a breadthfirst manner. The eligible grid faces are stored in a doubly connected edge list, using which the faces are finally merged to derive the isothetic polygons parallel to the coordinate planes, thereby obtaining the orthogonal cover of the object. The complexity of the cover decreases with increasing grid size. The algorithm requires computations in integer domain only and runs in a time linear in the number of voxels constituting the object surface. Experimental results demonstrate the effectiveness of the algorithm.

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|).

We present polynomial-time algorithms for computing an embedding of a planar graph that minimizes the outerplanarity, or the width, or the radius, or some other measures of distance to the outer face. On the other hand, we show it is NP-hard to compute an embedding that minimizes the diameter of the dual graph.

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.

We propose a data structure for maintaining 2-edge connectivity information dynamically in a planar graph. The data structure requires linear storage and preprocessing time for its construction, supports online updates (insertion and deletion of an edge) in O(log2n) time, and answers a query (whether two vertices are in the same 2-connected component) in O(log n) time. The previous best algorithm for this problem required O(log3n) time for updates.

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.

In practice, there often arises the problem of drawing in the plane graphs which exist, say, in the form of electric networks or time schedules, without any crossing. Such an embedding without crossing is important for the design of printed circuits. If all of the components of an electric network are left unconsidered, the graph G of the network remains and the embedding of this yields a solution to the problem.

This paper represents a strongly connected digraph as a doubly stochastic matrix. It then uses this doubly stochastic representation to prove several theorems concerning the critical arcs of strongly connected graphs. Definitions and notation. The definitions concerning matrix theory for the most part may be found in (3). All others will be given below.