Combinatorial pseudo-triangulations

We prove that a planar graph is generically rigid in the plane if and only if it can be embedded as a pseudo-triangulation. This generalizes the main result of [Haas et al. Planar minimally rigid graphs and pseudo-triangulations, Comput. Geom. 31(1–2) (2005) 31–61] which treats the minimally generically rigid case.The proof uses the concept of combinatorial pseudo-triangulation, CPT, in the plane and has two main steps: showing that a certain “generalized Laman property” is a necessary and sufficient condition for a CPT to be “stretchable”, and showing that all generically rigid plane graphs admit a CPT assignment with that property.Additionally, we propose the study of CPTs on closed surfaces.     

The Polytope of Non-Crossing Graphs on a Planar Point Set

For any set A of n points in ², we define a (3n - 3)-dimensional simple polyhedron whose face poset is isomorphic to the poset of non-crossing marked graphs with vertex set A, where a marked graph is defined as a geometric graph together with a subset of its vertices. The poset of non-crossing graphs on A appears as the complement of the star of a face in that polyhedron. The polyhedron has a unique maximal bounded face, of dimension 2n_i + n - 3 where n_i is the number of points of A in the interior of conv (A). The vertices of this polytope are all the pseudo-triangulations of A, and the edges are flips of two types: the traditional diagonal flips (in pseudo-triangulations) and the removal or insertion of a single edge. As a by-product of our construction we prove that all pseudo-triangulations are infinitesimally rigid graphs.     

Enumerating Constrained Non-crossing Minimally Rigid Frameworks

In this paper we present an algorithm for enumerating without repetitions all the non-crossing generically minimally rigid bar-and-joint frameworks under edge constraints, which we call constrained non-crossing Laman frameworks, on a given set of n points in the plane. Our algorithm is based on the reverse search paradigm of Avis and Fukuda. It generates each output graph in O(n ⁴) time and O(n) space, or, with a slightly different implementation, in O(n ³) time and O(n ²) space. In particular, we obtain that the set of all the constrained non-crossing Laman frameworks on a given point set is connected by flips which preserve the Laman property. D. Avis’s research was supported by NSERC and FQRNT grants. N. Katoh’s, M. Ohsaki’s and S.-i. Tanigawa’s research was supported by NEXT Grant-in-Aid for Scientific Research on priority areas of New Horizons in Computing. I. Streinu’s research was supported by NSF grant CCF-0430990 and NSF-DARPA CARGO CCR-0310661.     

Fast Enumeration Algorithms for Non-crossing Geometric Graphs

A non-crossing geometric graph is a graph embedded on a set of points in the plane with non-crossing straight line segments. In this paper we present a general framework for enumerating non-crossing geometric graphs on a given point set. Applying our idea to specific enumeration problems, we obtain faster algorithms for enumerating plane straight-line graphs, non-crossing spanning connected graphs, non-crossing spanning trees, and non-crossing minimally rigid graphs. Our idea also produces efficient enumeration algorithms for other graph classes, for which no algorithm has been reported so far, such as non-crossing matchings, non-crossing red-and-blue matchings, non-crossing k-vertex or k-edge connected graphs, or non-crossing directed spanning trees. The proposed idea is relatively simple and potentially applies to various other problems of non-crossing geometric graphs.     

The Planar Slope Number of Planar Partial 3-Trees of Bounded Degree

It is known that every planar graph has a planar embedding where edges are represented by non-crossing straight-line segments. We study the planar slope number, i.e., the minimum number of distinct edge-slopes in such a drawing of a planar graph with maximum degree Δ. We show that the planar slope number of every planar partial 3-tree and also every plane partial 3-tree is at most O(Δ ⁵). In particular, we answer the question of Dujmovi? et al. (Comput Geom 38(3):194–212, 2007) whether there is a function f such that plane maximal outerplanar graphs can be drawn using at most f(Δ) slopes.     

Non-Crossing Tableaux

In combinatorics there is a well-known duality between non-nesting and non-crossing objects. In algebra there are many objects which are standard, for example, standard Young tableaux, standard monomials, and standard bitableaux. We adopt a point of view that these standard objects are really non-nesting, and we find their non-crossing counterparts.     

Pointed drawings of planar graphs

We study the problem how to draw a planar graph crossing-free such that every vertex is incident to an angle greater than π. In general a plane straight-line drawing cannot guarantee this property. We present algorithms which construct such drawings with either tangent-continuous biarcs or quadratic Bézier curves (parabolic arcs), even if the positions of the vertices are predefined by a given plane straight-line drawing of the graph. Moreover, the graph can be drawn with circular arcs if the vertices can be placed arbitrarily. The topic is related to non-crossing drawings of multigraphs and vertex labeling.     

Plane Embeddings of Planar Graph Metrics

Embedding metrics into constant-dimensional geometric spaces, such as the Euclidean plane, is relatively poorly understood. Motivated by applications in visualization, ad-hoc networks, and molecular reconstruction, we consider the natural problem of embedding shortest-path metrics of unweighted planar graphs (planar graph metrics) into the Euclidean plane. It is known that, in the special case of shortest-path metrics of trees, embedding into the plane requires distortion in the worst case [M1], [BMMV], and surprisingly, this worst-case upper bound provides the best known approximation algorithm for minimizing distortion. We answer an open question posed in this work and highlighted by Matousek [M3] by proving that some planar graph metrics require distortion in any embedding into the plane, proving the first separation between these two types of graph metrics. We also prove that some planar graph metrics require distortion in any crossing-free straight-line embedding into the plane, suggesting a separation between low-distortion plane embedding and the well-studied notion of crossing-free straight-line planar drawings. Finally, on the upper-bound side, we prove that all outerplanar graph metrics can be embedded into the plane with distortion, generalizing the previous results on trees (both the worst-case bound and the approximation algorithm) and building techniques for handling cycles in plane embeddings of graph metrics.     

On the Enumeration of Non-Crossing Pairings of Well-Balanced Binary Strings

A non-crossing pairing on a binary string pairs ones and zeroes such that the arcs representing the pairings are non-crossing. A binary string is well-balanced if it is of the form ${1^{a_1} 0^{a_1}1^{a_2} 0^{a_2} . . .1^{a_r} 0^{a_r}}$ . In this paper we establish connections between non-crossing pairings of well-balanced binary strings and various lattice paths in plane. We show that for well-balanced binary strings with a ₁ ≤ a ₂ ≤  . . . ≤  a _r , the number of non-crossing pairings is equal to the number of lattice paths on the plane with certain right boundary, and hence can be enumerated by differential Goncarov polynomials. For the regular binary strings S =  (1 ^k 0 ^k ) ⁿ , the number of non-crossing pairings is given by the (k + 1)-Catalan numbers. We present a simple bijective proof for this case.     

Flips in planar graphs

We review results concerning edge flips in planar graphs concentrating mainly on various aspects of the following problem: Given two different planar graphs of the same size, how many edge flips are necessary and sufficient to transform one graph into another? We overview both the combinatorial perspective (where only a combinatorial embedding of the graph is specified) and the geometric perspective (where the graph is embedded in the plane, vertices are points and edges are straight-line segments). We highlight the similarities and differences of the two settings, describe many extensions and generalizations, highlight algorithmic issues, outline several applications and mention open problems.     

CYCLE SPACES OF GRAPHS ON THE SPHERE AND THE PROJECTIVE PLANE

Cycle base theory of a graph has been well studied in abstract mathematical field such matroid theory as Whitney and Tutte did and found many applications in pratical uses such as electric circuit theory and structure analysis, etc. In this paper graph embedding theory is used to investigate cycle base structures of a 2-(edge)-connected graph on the sphere and the projective plane and it is shown that short cycles do generate the cycle spaces in the case of ““““small face-embeddings““““. As applications the authors find the exact formulae for the minimum lengthes of cycle bases of some types of graphs and present several known results. Infinite examples shows that the conditions in their main results are best possible and there are many 3-connected planar graphs whose minimum cycle bases can not be determined by the planar formulae but may be located by re-embedding them into the projective plane.     

A full characterization of invariant embeddability of unimodular planar graphs

When can a unimodular random planar graph be drawn in the Euclidean or the hyperbolic plane in a way that the distribution of the random drawing is isometry-invariant? This question was answered for one-ended unimodular graphs in Benjamini and Timar, using the fact that such graphs automatically have locally finite (simply connected) drawings into the plane. For the case of graphs with multiple ends the question was left open. We revisit Halin's graph theoretic characterization of graphs that have a locally finite embedding into the plane. Then we prove that such unimodular random graphs do have a locally finite invariant embedding into the Euclidean or the hyperbolic plane, depending on whether the graph is amenable or not.     

Acute Triangulations of Polygons

This paper proposes a combinatorial approach to planning non-colliding trajectories for a polygonal bar-and-joint framework with n vertices. It is based on a new class of simple motions induced by expansive one-degree-of-freedom mechanisms, which guarantee noncollisions by moving all points away from each other. Their combinatorial structure is captured by pointed pseudo-triangulations, a class of embedded planar graphs for which we give several equivalent characterizations and exhibit rich rigidity theoretic properties. The main application is an efficient algorithm for the Carpenter’s Rule Problem: convexify a simple bar-and-joint planar polygonal linkage using only non-self-intersecting planar motions. A step of the algorithm consists in moving a pseudo-triangulation-based mechanism along its unique trajectory in configuration space until two adjacent edges align. At the alignment event, a local alteration restores the pseudo-triangulation. The motion continues for O(n3) steps until all the points are in convex position. An erratum to this article is available at .     

Bipartite partial duals and circuits in medial graphs

It is well known that a plane graph is Eulerian if and only if its geometric dual is bipartite. We extend this result to partial duals of plane graphs. We then characterize all bipartite partial duals of a plane graph in terms of oriented circuits in its medial graph.     

General theoretical results on rectilinear embedability of graphs

In the design of certain kinds of electronic circuits the following question arises: given a non-negative integerk, what graphs admit of a plane embedding such that every edge is a broken line formed by horizontal and vertical segments and having at mostk bends? Any such graph is said to bek-rectilinear. No matter whatk is, an obvious necessary condition fork-rectilinearity is that the degree of each vertex does not exceed four. Our main result is that every planar graphH satisfying this condition is 3-rectilinear: in fact, it is 2-rectilinear with the only exception of the octahedron. We also outline a polynomial-time algorithm which actually constructs a plane embedding ofH with at most 2 bends (3 bends ifH is the octahedron) on each edge. The resulting embedding has the property that the total number of bends does not exceed 2n, wheren is the number of vertices ofH.     

平面图书式嵌入综述

图书式嵌入问题主要起源于大型集成电路(VLSI)设计和多层线路板印刷(PCBs)设计等诸多领域,有广泛的应用价值.图的书式嵌入是将图的点集排在一条直线上(书脊)且将边嵌入到以书脊为边界的半平面上(页)使得同页中的边互不相交.其研究的一个重要参数是页数(满足条件所需的最小页数),该问题是NP-困难的.本文主要综述平面图书式嵌入问题的相关研究.     

Maximum Genus of Strong Embeddings

The strong embedding conjecture states that any 2-connected graph has a strong embedding on some surface. It implies the circuit double cover conjecture: Any 2-connected graph has a circuit double cover.Conversely, it is not true. But for a 3-regular graph, the two conjectures are equivalent. In this paper, a characterization of graphs having a strong embedding with exactly 3 faces, which is the strong embedding of maximum genus, is given. In addition, some graphs with the property are provided. More generally, an upper bound of the maximum genus of strong embeddings of a graph is presented too. Lastly, it is shown that the interpolation theorem is true to planar Halin graph.     

The non-solvability by radicals of generic 3-connected planar Laman graphs

We show that planar embeddable -connected Laman graphs are generically non-soluble. A Laman graph represents a configuration of points on the Euclidean plane with just enough distance specifications between them to ensure rigidity. Formally, a Laman graph is a maximally independent graph, that is, one that satisfies the vertex-edge count together with a corresponding inequality for each subgraph. The following main theorem of the paper resolves a conjecture of Owen (1991) in the planar case. Let be a maximally independent -connected planar graph, with more than 3 vertices, together with a realisable assignment of generic distances for the edges which includes a normalised unit length (base) edge. Then, for any solution configuration for these distances on a plane, with the base edge vertices placed at rational points, not all coordinates of the vertices lie in a radical extension of the distance field.

     

A survey on book-embedding of planar graphs

The book-embedding problem arises in several area, such as very large scale integration (VLSI) design and routing multilayer printed circuit boards (PCBs). It can be used into various practical application fields. A book embedding of a graph G is an embedding of its vertices along the spine of a book, and an embedding of its edges to the pages such that edges embedded on the same page do not intersect. The minimum number of pages in which a graph G can be embedded is called the pagenumber or book-thickness of the graph G. It is an important measure of the quality for book-embedding. It is NP-hard to research the pagenumber of book-embedding for a graph G. This paper summarizes the studies on the book-embedding of planar graphs in recent years.     

On convex embeddings of planar 3‐connected graphs

A well‐known Tutte's theorem claims that every 3‐connected planar graph has a convex embedding into the plane. Tutte's arguments also show that, moreover, for every nonseparating cycle C of a 3‐connected graph G, there exists a convex embedding of G such that C is a boundary of the outer face in this embedding. We give a simple proof of this last result. Our proof is based on the fact that a 3‐connected graph admits an ear assembly having some special properties with respect to the nonseparating cycles of the graph. This fact may be interesting and useful in itself. © 2000 John Wiley & Sons, Inc. J. Graph Theory 33: 120–124, 2000