A correspondence between scene analysis and motions of frameworks

For over 100 years there has been a known correspondence between plane pictures of spherical polyhedra and static stresses in bar and joint frameworks with planar graphs. We define a new map from any plane picture of a general scene to a corresponding plate and bar framework in the plane. This map, and its return map, give a simple isomorphism between the space of scenes over the picture and the space of instantaneous motions of the framework. When two simple equivalence relations on the pictures and on the frameworks are introduced, the maps define an isomorphism of the equivalence clases which permits the full translation of questions, techniques and theorems between the two fields of study. A direct geometric interpretation of this correspondence is described and an extension to systems with occlusion and tensegrity (systems of inequalities) is presented. The analogous patterns in higher dimensions are described, yielding a correspondence between motions of bar and body frameworks in 3-space and 6-dimensional scenes over 5-dimensional pictures.     

Some basic properties of planar Singer groups

A planar Singer group is a collineation group of a finite (in this article) projective plane acting regularly on the points of the plane. Theorem 1 gives a characterization of abelian planar Singer groups. This leads to a necessary and sufficient condition for an inner automorphism to be a multiplier. The Sylow 2-structure of a multiplier group and some of its consequences are given in Theorem 3. One important result in studying multipliers of an abelian Singer group is the existence of a common fixed line. We extend this to an arbitrary planar Singer group in Theorem 4. Theorem 5 studies the order of an abelian group of multiplers. If this order equals to the order of the plane plus 1, then the number of points of the plane is a prime. If this order is odd, then it is at most the planar order plus 1.Partially supported by a NSA grant.     

Counting unrooted maps on the plane

A planar map is a 2-cell embedding of a connected planar graph, loops and parallel edges allowed, on the sphere. A plane map is a planar map with a distinguished outside (“infinite”) face. An unrooted map is an equivalence class of maps under orientation-preserving homeomorphism, and a rooted map is a map with a distinguished oriented edge. Previously we obtained formulae for the number of unrooted planar n-edge maps of various classes, including all maps, non-separable maps, eulerian maps and loopless maps. In this article, using the same technique we obtain closed formulae for counting unrooted plane maps of all these classes and their duals. The corresponding formulae for rooted maps are known to be all sum-free; the formulae that we obtain for unrooted maps contain only a sum over the divisors of n. We count also unrooted two-vertex plane maps.     

Visibility Drawings of Plane 3-Trees with Minimum Area

A visibility drawing of a plane graph G is a drawing of G where each vertex is drawn as a horizontal line segment and each edge is drawn as a vertical line segment such that the line segments use only grid points as their endpoints. The area of a visibility drawing is the area of the smallest rectangle on the grid which encloses the drawing. A minimum-area visibility drawing of a plane graph G is a visibility drawing of G where the area is the minimum among all possible visibility drawings of G. The area minimization for grid visibility representation of planar graphs is NP-hard. However, the problem can be solved for a fixed planar embedding of a hierarchically planar graph in quadratic time. In this paper, we give a polynomial-time algorithm to obtain minimum-area visibility drawings of plane 3-trees.     

An algorithm for constructing star-shaped drawings of plane graphs

A straight-line planar drawing of a plane graph is called a convex drawing if every facial cycle is drawn as a convex polygon. Convex drawings of graphs is a well-established aesthetic in graph drawing, however not all planar graphs admit a convex drawing. Tutte [W.T. Tutte, Convex representations of graphs, Proc. of London Math. Soc. 10 (3) (1960) 304–320] showed that every triconnected plane graph admits a convex drawing for any given boundary drawn as a convex polygon. Thomassen [C. Thomassen, Plane representations of graphs, in: Progress in Graph Theory, Academic Press, 1984, pp. 43–69] gave a necessary and sufficient condition for a biconnected plane graph with a prescribed convex boundary to have a convex drawing.In this paper, we initiate a new notion of star-shaped drawing of a plane graph as a straight-line planar drawing such that each inner facial cycle is drawn as a star-shaped polygon, and the outer facial cycle is drawn as a convex polygon. A star-shaped drawing is a natural extension of a convex drawing, and a new aesthetic criteria for drawing planar graphs in a convex way as much as possible. We give a sufficient condition for a given set A of corners of a plane graph to admit a star-shaped drawing whose concave corners are given by the corners in A, and present a linear time algorithm for constructing such a star-shaped drawing.     

Improvements on the density of maximal 1‐planar graphs

A graph is 1‐planar if it can be drawn in the plane such that each edge is crossed at most once. A graph, together with a 1‐planar drawing is called 1‐plane. A graph is maximal 1‐planar (1‐plane), if we cannot add any missing edge so that the resulting graph is still 1‐planar (1‐plane). Brandenburg et al. showed that there are maximal 1‐planar graphs with only edges and maximal 1‐plane graphs with only edges. On the other hand, they showed that a maximal 1‐planar graph has at least edges, and a maximal 1‐plane graph has at least edges. We improve both lower bounds to .     

Algebraic characterizations of outerplanar and planar graphs

A drawing of a graph in the plane is even if nonadjacent edges have an even number of intersections. Hanani’s theorem characterizes planar graphs as those graphs that have an even drawing. In this paper we present an algebraic characterization of graphs that have an even drawing. Together with Hanani’s theorem this yields an algebraic characterization of planar graphs. We will also present algebraic characterizations of subgraphs of paths, and of outerplanar graphs.     

Nonexistence of certain complete minimal surfaces with planar ends

In this paper we prove that two lines bounding an immersed minimal surface in a slab in R ³ homeomorphic to a compact Riemann surface minus two disks and a finite number of points must be parallel. This theorem is extended to a higher dimensional minimal hypersurface. Also it is proved that if the Gauss map of a complete embedded minimal surface of finite total curvature at a planar end has order two, then the intersection of the surface with the plane asymptotic to the planar end cannot admit a one-to-one orthogonal projection onto any line in the plane. Received: November 26, 1998     

Projective-planar graphs with even duals

Let G be a connected graph which is projective-planar but is not planar. It will be shown that G can be embedded in the projective plane so that it has only even faces if and only if either G is bipartite or its canonical bipartite covering is planar and that such an embedding is unique if G is 3-connected.     

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.     

Establishing order in planar subdivisions

A planar subdivision is the partition of the plane induced by an embedded planar graph. A representation of such a subdivision isordered if, for each vertexv of the associated graphG, the (say) clockwise sequence of edges in the embedding ofG incident withv appears explicitly.The worst-case complexity of establishing order in a planar subdivision, i.e., converting an unordered representation into an ordered one, is shown to be (n + log (G)), wheren is the size (number of vertices) of the underlying graphG and (G) is (essentially) the number of topologically distinct embeddings ofG in the plane.This work was supported by the National Science and Engineering Research Council of Canada under Grant A3583. A preliminary version of this paper appeared in theProceedings of the Third Annual ACM Symposium on Computational Geometry.     

第二大特征值小于$\frac{\sqrt{5}-1}{2}$的平面图

若能将图$G$画在一个平面上,使得任何两条边仅在顶点处相交,则称$G$是平面图.本文刻画了第二大特征值小于$\frac{\sqrt{5}-1}{2}$的所有无孤立点的平面图.     

Cycle Covers of Planar 2-Edge-Connected Graphs

A graph with n vertices is said to have a small cycle cover provided its edges can be covered with at most (2n ? 1)/3 cycles. Bondy [2] has conjectured that every 2-connected graph has a small cycle cover. In [3] Lai and Lai prove Bondy’s conjecture for plane triangulations. In [1] the author extends this result to all planar 3-connected graphs, by proving that they can be covered by at most (n + 1)/2 cycles. In this paper we show that Bondy’s conjecture holds for all planar 2-connected graphs. We also show that all planar 2-edge-connected graphs can be covered by at most (3n ? 3)/4 cycles and we show an infinite family of graphs for which this bound is attained.     

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.     

Geodesic Webs on a Two-Dimensional Manifold and Euler Equations

We prove that any planar 4-web defines a unique projective structure in the plane in such a way that the leaves of the web foliations are geodesics of this projective structure. We also find conditions for the projective structure mentioned above to contain an affine symmetric connection, and conditions for a planar 4-web to be equivalent to a geodesic 4-web on an affine symmetric surface. Similar results are obtained for planar d-webs, d>4, provided that additional d−4 second-order invariants vanish.     

Convex drawings of hierarchical planar graphs and clustered planar graphs

In this paper, we present results on convex drawings of hierarchical graphs and clustered graphs. A convex drawing is a planar straight-line drawing of a plane graph, where every facial cycle is drawn as a convex polygon. Hierarchical graphs and clustered graphs are useful graph models with structured relational information. Hierarchical graphs are graphs with layering structures; clustered graphs are graphs with recursive clustering structures.We first present the necessary and sufficient conditions for a hierarchical plane graph to admit a convex drawing. More specifically, we show that the necessary and sufficient conditions for a biconnected plane graph due to Thomassen [C. Thomassen, Plane representations of graphs, in: J.A. Bondy, U.S.R. Murty (Eds.), Progress in Graph Theory, Academic Press, 1984, pp. 43–69] remains valid for the case of a hierarchical plane graph. We then prove that every internally triconnected clustered plane graph with a completely connected clustering structure admits a “fully convex drawing,” a planar straight-line drawing such that both clusters and facial cycles are drawn as convex polygons. We also present algorithms to construct such convex drawings of hierarchical graphs and clustered graphs.     

Oriented Coloring of Triangle-Free Planar Graphs and 2-Outerplanar Graphs

A graph is planar if it can be embedded on the plane without edge-crossings. A graph is 2-outerplanar if it has a planar embedding such that the subgraph obtained by removing the vertices of the external face is outerplanar (i.e. with all its vertices on the external face). An oriented k-coloring of an oriented graph G is a homomorphism from G to an oriented graph H of order k. We prove that every oriented triangle-free planar graph has an oriented chromatic number at most 40, that improves the previous known bound of 47 [Borodin, O. V. and Ivanova, A. O., An oriented colouring of planar graphs with girth at least 4, Sib. Electron. Math. Reports, vol. 2, 239–249, 2005]. We also prove that every oriented 2-outerplanar graph has an oriented chromatic number at most 40, that improves the previous known bound of 67 [Esperet, L. and Ochem, P. Oriented colouring of 2-outerplanar graphs, Inform. Process. Lett., vol. 101(5), 215–219, 2007].     

One-Parameter Homothetic Motion in the Hyperbolic Plane and Euler-Savary Formula

In [10] one-parameter planar motion was first introduced and the relations between absolute, relative, sliding velocities (and accelerations) in the Euclidean plane \mathbb E²{{\mathbb E}^2} were obtained. Moreover, the relations between the complex velocities of one-parameter motion in the complex plane were provided by [10]. One-parameter planar homothetic motion was defined in the complex plane, [9]. In this paper, analogous to homothetic motion in the complex plane given by [9], one-parameter planar homothetic motion is defined in the hyperbolic plane. Some characteristic properties about the velocity vectors, the acceleration vectors and the pole curves are given. Moreover, in the case of homothetic scale h identically equal to 1, the results given in [15] are obtained as a special case. In addition, three hyperbolic planes, of which two are moving and the other one is fixed, are taken into consideration and a canonical relative system for one-parameter planar hyperbolic homothetic motion is defined. Euler-Savary formula, which gives the relationship between the curvatures of trajectory curves, is obtained with the help of this relative system.     

Generating unlabeled connected cubic planar graphs uniformly at random

We present an expected polynomial time algorithm to generate an unlabeled connected cubic planar graph uniformly at random. We first consider rooted connected cubic planar graphs, i.e., we count connected cubic planar graphs up to isomorphisms that fix a certain directed edge. Based on decompositions along the connectivity structure, we derive recurrence formulas for the exact number of rooted cubic planar graphs. This leads to rooted 3‐connected cubic planar graphs, which have a unique embedding on the sphere. Special care has to be taken for rooted graphs that have a sense‐reversing automorphism. Therefore we introduce the concept of colored networks, which stand in bijective correspondence to rooted 3‐connected cubic planar graphs with given symmetries. Colored networks can again be decomposed along the connectivity structure. For rooted 3‐connected cubic planar graphs embedded in the plane, we switch to the dual and count rooted triangulations. Since all these numbers can be evaluated in polynomial time using dynamic programming, rooted connected cubic planar graphs can be generated uniformly at random in polynomial time by inverting the decomposition along the connectivity structure. To generate connected cubic planar graphs without a root uniformly at random, we apply rejection sampling and obtain an expected polynomial time algorithm. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Ammann bars and quasicrystals

In 1988 Danzer [3] constructed a family of four tetrahedra which allows—with certain matching conditions—only aperiodic tilings. By analogy with the Ammann bars of planar Penrose tilings we define Ammann bars in space in the form of planar Penrose tilings we define Ammann bars in space in the form of plane sections of the four tetrahedra. If we require that the plane sections continue as planes across the faces of the tilings, we obtain an alternative matching condition, thus answering a question of Danzer.