Rectangular-radial drawings of cubic plane graphs

Rectangular drawings and rectangular duals can be naturally extended to other surfaces. In this paper, we extend rectangular drawings and rectangular duals to drawings on a cylinder. The extended drawings are called rectangular-radial drawings and rectangular-radial duals. Rectangular-radial drawings correspond to periodic rectangular tilings of a 1-dimensional strip. We establish a necessary and sufficient condition for plane graphs with maximum degree 3 to have rectangular-radial drawings and a necessary and sufficient condition for triangulated plane graphs to have rectangular-radial duals. Furthermore, we present three linear time algorithms under three different conditions for finding a rectangular-radial drawing for a given cubic plane graph, if one exists.     

Rectangular drawings of plane graphs without designated corners

This paper addresses the problem of finding rectangular drawings of plane graphs, in which each vertex is drawn as a point, each edge is drawn as a horizontal or a vertical line segment, and the contour of each face is drawn as a rectangle. A graph is a 2–3 plane graph if it is a plane graph and each vertex has degree 3 except the vertices on the outer face which have degree 2 or 3. A necessary and sufficient condition for the existence of a rectangular drawing has been known only for the case where exactly four vertices of degree 2 on the outer face are designated as corners in a 2–3 plane graph G. In this paper we establish a necessary and sufficient condition for the existence of a rectangular drawing of G for the general case in which no vertices are designated as corners. We also give a linear-time algorithm to find a rectangular drawing of G if it exists.     

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.     

Edge‐face coloring of plane graphs with maximum degree nine

An edge‐face coloring of a plane graph with edge set E and face set F is a coloring of the elements of E∪F so that adjacent or incident elements receive different colors. Borodin [Discrete Math 128(1–3):21–33, 1994] proved that every plane graph of maximum degree Δ?10 can be edge‐face colored with Δ + 1 colors. We extend Borodin's result to the case where Δ = 9. © 2010 Wiley Periodicals, Inc. J Graph Theory 66:332‐346, 2011     

Rectilinear drawings of graphs

We consider graphs drawn in the plane such that every edge crosses at most one other edge. We characterize, in terms of two forbidden sub-configurations, which of these graphs are equivalent to drawings such that all edges are straight line segments. As a consequence we obtain a complete characterization of the pairs of dual graphs that can be represented as geometric dual graphs such that all edges except one are straight line segments.     

Absolute graphs with prescribed endomorphism monoid

We consider endomorphism monoids of graphs. It is well-known that any monoid can be represented as the endomorphism monoid M of some graph Γ with countably many colors. We give a new proof of this theorem such that the isomorphism between the endomorphism monoid $\mathop{\rm End}\nolimits (\Gamma)We consider endomorphism monoids of graphs. It is well-known that any monoid can be represented as the endomorphism monoid M of some graph Γ with countably many colors. We give a new proof of this theorem such that the isomorphism between the endomorphism monoid and M is absolute, i.e. holds in any generic extension of the given universe of set theory. This is true if and only if |M|,|Γ| are smaller than the first Erdős cardinal (which is known to be strongly inaccessible). We will encode Shelah’s absolutely rigid family of trees (Isr. J. Math. 42(3), 177–226, 1982) into Γ. The main result will be used to construct fields with prescribed absolute endomorphism monoids, see G?bel and Pokutta (Shelah’s absolutely rigid trees and absolutely rigid fields, in preparation). This work was supported by the project No. I-706-54.6/2001 of the German-Israeli Foundation for Scientific Research & Development and a fellowship within the Postdoc-Programme of the German Academic Exchange Service (DAAD).     

On graphs with prescribed median I

The distance of a vertex u in a connected graph H is the sum of all the distances from u to the other vertices of H. The median M(H) of H is the subgraph of H induced by the vertices of minimum distance. For any graph G, let f(G) denote the minimum order of a connected graph H satisfying M(H) ? G. It is shown that if G has n vertices and minimum degree δ then f(G) ? 2n ? δ + 1. Graphs having both median and center prescribed are constructed. It is also shown that if the vertices of a K_r are removed from a graph H, then at most r components of the resulting graph contain median vertices of H.     

Extremal graphs with prescribed covering number

We show that any connected graph with ? edges and covering number β satisfies the inequality ? ≥ 2β ? 1. The graphs for which equality holds are characterized.     

Light graphs in families of polyhedral graphs with prescribed minimum degree, face size, edge and dual edge weight

A graph H is defined to be light in a family H of graphs if there exists a finite number φ(H,H) such that each G∈H which contains H as a subgraph, contains also a subgraph K≅H such that the Δ_G(K)≤φ(H,H). We study light graphs in families of polyhedral graphs with prescribed minimum vertex degree δ, minimum face degree ρ, minimum edge weight w and dual edge weight w^∗. For those families, we show that there exists a variety of small light cycles; on the other hand, we also present particular constructions showing that, for certain families, the spectrum of short cycles contains irregularly scattered cycles that are not light.     

Killing graphs with prescribed mean curvature

It is proved the existence and uniqueness of Killing graphs with prescribed mean curvature in a large class of Riemannian manifolds. M. Dajczer was partially supported by Procad, CNPq and Faperj. P. A. Hinojosa was partially supported by PADCT/CT-INFRA/CNPq/MCT Grant #620120/2004-5. J. H. de Lira was partially supported by CNPq and Funcap.     

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.     

Monotone drawings of planar graphs

Let G be a graph drawn in the plane so that its edges are represented by x‐monotone curves, any pair of which cross an even number of times. We show that G can be redrawn in such a way that the x‐coordinates of the vertices remain unchanged and the edges become non‐crossing straight‐line segments. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 39–47, 2004     

Orientations of infinite graphs with prescribed edge-connectivity

We prove a decomposition result for locally finite graphs which can be used to extend results on edge-connectivity from finite to infinite graphs. It implies that every 4k-edge-connected graph G contains an immersion of some finite 2k-edge-connected Eulerian graph containing any prescribed vertex set (while planar graphs show that G need not containa subdivision of a simple finite graph of large edge-connectivity). Also, every 8k-edge connected infinite graph has a k-arc-connected orientation, as conjectured in 1989.     

Existence of graphs with prescribed mean distance

It is shown that for each rational number t ≥ 1 there exist infinitely many graphs with mean distance equal to t. For a graph G, define the mean distance μ(G) by . In an earlier issue of this journal, J. Plesník [3, Theorem 9] showed that, given real numbers t ≥ 1 and ? > 0, there exists a graph G with |μ(G)?t| < ?. Furthermore, he asked [3, p. 19]: Given a rational number t ≥ 1, does there exist a graph G with μ(G) = t? We answer this question in the affirmative by proving:     

Convex drawings of graphs with non-convex boundary constraints

In this paper, we study a new problem of convex drawing of planar graphs with non-convex boundary constraints, and call a drawing in which every inner-facial cycle is drawn as a convex polygon an inner-convex drawing. It is proved that every triconnected plane graph with the boundary fixed with a star-shaped polygon whose kernel has a positive area admits an inner-convex drawing. We also prove that every four-connected plane graph whose boundary is fixed with a crown-shaped polygon admits an inner-convex drawing. We present linear time algorithms to construct inner-convex drawings for both cases.