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.     

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 fixing boundary points of transitive hyperbolic graphs

We show that there is no one-ended, locally finite, planar, hyperbolic graph such that the stabilizer of one of its hyperbolic boundary points acts transitively on the vertices of the graph. This gives a partial answer to a question by Kaimanovich and Woess.     

平面图书式嵌入综述

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

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.     

Spanning trees in hyperbolic graphs

We construct spanning trees in locally finite hyperbolic graphs that represent their hyperbolic compactification in a good way: so that the tree has at least one but at most a bounded number of disjoint rays to each boundary point. As a corollary we extend a result of Gromov which says that from every hyperbolic graph with bounded degrees one can construct a tree (disjoint from the graph) with a continuous surjection from the ends of the tree onto the hyperbolic boundary such that the surjection is finite-to-one. We shall construct a tree with these properties as a subgraph of the hyperbolic graph, which in addition is also a spanning tree of that graph.     

Rectangular and visibility representations of infinite planar graphs

We provide a new method for extending results on finite planar graphs to the infinite case. Thus a result of Ungar on finite graphs has the following extension: Every infinite, planar, cubic, cyclically 4‐edge‐connected graph has a representation in the plane such that every edge is a horizontal or vertical straight line segment, and such that no two edges cross. A result of Tamassia and Tollis extends as follows: Every countably infinite planar graph is a subgraph of a visibility graph. Furthermore, every locally finite, 2‐connected, planar graph is a visibility graph. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 257–265, 2006     

Spectra of toroidal graphs

An n-fold periodic locally finite graph in the Euclidean n-space may be considered the parent of an infinite class of n-dimensional toroidal finite graphs. An elementary method is developed that allows the characteristic polynomials of these graphs to be factored, in a uniform manner, into smaller polynomials, all of the same size.Applied to the hexagonal tessellation of the plane (the graphite sheet), this method enables the spectra and corresponding orthonormal eigenvector systems for all toroidal fullerenes and (3, 6)-cages to be explicitly calculated. In particular, a conjecture of P.W. Fowler on the spectra of (3, 6)-cages is proved.     

Closed 2-cell embeddings of graphs with no V8-minors

A closed 2-cell embedding of a graph embedded in some surface is an embedding such that each face is bounded by a cycle in the graph. The strong embedding conjecture says that every 2-connected graph has a closed 2-cell embedding in some surface. In this paper, we prove that any 2-connected graph without V₈ (the Möbius 4-ladder) as a minor has a closed 2-cell embedding in some surface. As a corollary, such a graph has a cycle double cover. The proof uses a classification of internally-4-connected graphs with no V₈-minor (due to Kelmans and independently Robertson), and the proof depends heavily on such a characterization.     

Hyperbolic and parabolic packings

The contacts graph, or nerve, of a packing, is a combinatorial graph that describes the combinatorics of the packing. LetG be the 1-skeleton of a triangulation of an open disk.G is said to be CP parabolic (resp. CP hyperbolic) if there is a locally finite disk packingP in the plane (resp. the unit disk) with contacts graphG. Several criteria for deciding whetherG is CP parabolic or CP hyperbolic are given, including a necessary and sufficient combinatorial criterion. A criterion in terms of the random walk says that if the random walk onG is recurrent, theG is CP parabolic. Conversely, ifG has bounded valence and the random walk onG is transient, thenG is CP hyperbolic. We also give a new proof thatG is either CP parabolic or CP hyperbolic, but not both. The new proof has the advantage of being applicable to packings of more general shapes. Another new result is that ifG is CP hyperbolic andD is any simply connected proper subdomain of the plane, then there is a disk packingP with contacts graphG such thatP is contained and locally finite inD. Both authors acknowledge support by NSF grants. The first author was also supported by the A. Sloan Research Fellowship.     

Upward straight-line embeddings of directed graphs into point sets

In this paper we study the problem of computing an upward straight-line embedding of a planar DAG (directed acyclic graph) G into a point set S, i.e. a planar drawing of G such that each vertex is mapped to a point of S, each edge is drawn as a straight-line segment, and all the edges are oriented according to a common direction. In particular, we show that no biconnected DAG admits an upward straight-line embedding into every point set in convex position. We provide a characterization of the family of DAGs that admit an upward straight-line embedding into every convex point set such that the points with the largest and the smallest y-coordinate are consecutive in the convex hull of the point set. We characterize the family of DAGs that contain a Hamiltonian directed path and that admit an upward straight-line embedding into every point set in general position. We also prove that a DAG whose underlying graph is a tree does not always have an upward straight-line embedding into a point set in convex position and we describe how to construct such an embedding for a DAG whose underlying graph is a path. Finally, we give results about the embeddability of some sub-classes of DAGs whose underlying graphs are trees on point set in convex and in general position.     

Planar acyclic oriented graphs

A plane Hasse representation of an acyclic oriented graph is a drawing of the graph in the Euclidean plane such that all arcs are straight-line segments directed upwards and such that no two arcs cross. We characterize completely those oriented graphs which have a plane Hasse representation such that all faces are bounded by convex polygons. From this we derive the Hasse representation analogue, due to Kelly and Rival of Fary's theorem on straight-line representations of planar graphs and the Kuratowski type theorem of Platt for acyclic oriented graphs with only one source and one sink. Finally, we describe completely those acyclic oriented graphs which have a vertex dominating all other vertices and which have no plane Hasse representation, a problem posed by Trotter.     

Planar unit-distance graphs having planar unit-distance complement

A graph G=(V,E) is called a unit-distance graph in the plane if there is an embedding of V into the plane such that every pair of adjacent vertices are at unit distance apart. If an embedding of V satisfies the condition that two vertices are adjacent if and only if they are at unit distance apart, then G is called a strict unit-distance graph in the plane. A graph G is a (strict) co-unit-distance graph, if both G and its complement are (strict) unit-distance graphs in the plane. We show by an exhaustive enumeration that there are exactly 69 co-unit-distance graphs (65 are strict co-unit-distance graphs), 55 of which are connected (51 are connected strict co-unit-distance graphs), and seven are self-complementary.     

Sharp bounds on eigenvalues via spectral embedding based on signless Laplacians

Using spectral embedding based on the probabilistic signless Laplacian, we obtain bounds on the spectrum of transition matrices on graphs. As a consequence, we bound return probabilities and the uniform mixing time of simple random walk on graphs. In addition, spectral embedding is used in this article to bound the spectrum of graph adjacency matrices. Our method is adapted from Lyons and Oveis Gharan [13].     

Amenability,locally finite spaces,and bi-lipschitz embeddings

We define the isoperimetric constant for any locally finite metric space and we study the property of having isoperimetric constant equal to zero. This property, called Small Neighborhood property, clearly extends amenability to any locally finite space. Therefore, we start making a comparison between this property and other notions of amenability for locally finite metric spaces that have been proposed by Gromov, Lafontaine and Pansu, by Ceccherini-Silberstein, Grigorchuk and de la Harpe and by Block and Weinberger. We discuss possible applications of the property SN in the study of embedding a metric space into another one. In particular, we propose three results: we prove that a certain class of metric graphs that are isometrically embeddable into Hilbert spaces must have the property SN. We also show, by a simple example, that this result is not true replacing property SN with amenability. As a second result, we prove that many spaces with uniform bounded geometry having a bi-lipschitz embedding into Euclidean spaces must have the property SN. Finally, we prove a Bourgain-like theorem for metric trees: a metric tree with uniform bounded geometry and without property SN does not have bi-lipschitz embeddings into finite-dimensional Hilbert spaces.     

A characterization of projective-planar signed graphs

A signed graph has a plus or minus sign on each edge. A simple cycle is positive or negative depending on whether it contains an even or odd number of negative edges, respectively. We consider embeddings of a signed graph in the projective plane for which a simple cycle is essential if and only if it is negative. We characterize those signed graphs that have such a projective-planar embedding. Our characterization is in terms of a related signed graph formed by considering the theta subgraphs in the given graph.     

Characterization of curve map graphs

In this paper we provide a characterization of curve map graphs as defined by Gavril and Schönheim, and also give a recognition algorithm for them.A curve map graph is the dual of a map obtained by placing a finite number of two-way infinite Jordan curves in the Euclidean plane in such a way that each curve divides the plane into two regions, no two curves intersect in more than one point, and any two curves which intersect at a point cross at that point.Our method is based on Gavril and Schönheim's approach, but corrects several difficulties in their characterization.     

An Interlacing Technique for Spectra of Random Walks and Its Application to Finite Percolation Clusters

A comparison technique for random walks on finite graphs is introduced, using the well-known interlacing method. It yields improved return probability bounds. A key feature is the incorporation of parts of the spectrum of the transition matrix other than just the principal eigenvalue. As an application, an upper bound of the expected return probability of a random walk with symmetric transition probabilities is found. In this case, the state space is a random partial graph of a regular graph of bounded geometry and transitive automorphism group. The law of the random edge-set is assumed to be invariant with respect to some transitive subgroup of the automorphism group (‘invariant percolation’). Given that this subgroup is unimodular, it is shown that this invariance strengthens the upper bound of the expected return probability, compared with standard bounds such as those derived from the Cheeger inequality. The improvement is monotone in the degree of the underlying transitive graph.     

Strong embeddings of minimum genus

A “folklore conjecture, probably due to Tutte” (as described in [P.D. Seymour, Sums of circuits, in: Graph Theory and Related Topics (Proc. Conf., Univ. Waterloo, 1977), Academic Press, 1979, pp. 341-355]) asserts that every bridgeless cubic graph can be embedded on a surface of its own genus in such a way that the face boundaries are cycles of the graph. Sporadic counterexamples to this conjecture have been known since the late 1970s. In this paper we consider closed 2-cell embeddings of graphs and show that certain (cubic) graphs (of any fixed genus) have closed 2-cell embedding only in surfaces whose genus is very large (proportional to the order of these graphs), thus providing a plethora of strong counterexamples to the above conjecture. The main result yielding such counterexamples may be of independent interest.