A circular embedding of a graph in Euclidean 3-space

A spatial embedding of a graph G is an embedding of G into the 3-dimensional Euclidean space . J.H. Conway and C.McA. Gordon proved that every spatial embedding of the complete graph on 7 vertices contains a nontrivial knot. A linear spatial embedding of a graph is an embedding which maps each edge to a single straight line segment. In this paper, we construct a linear spatial embedding of the complete graph on 2n−1 (or 2n) vertices which contains the torus knot T(2n−5,2) (n4). A circular spatial embedding of a graph is an embedding which maps each edge to a round arc. We define the circular number of a knot as the minimal number of round arcs in among such embeddings of the knot. We show that a knot has circular number 3 if and only if the knot is a trefoil knot, and the figure-eight knot has circular number 4.     

Drawing planar graphs with circular arcs

In this paper we address the problem of drawing planar graphs with circular arcs while maintaining good angular resolution and small drawing area. We present a lower bound on the area of drawings in which edges are drawn using exactly one circular arc. We also give an algorithm for drawing n -vertex planar graphs such that the edges are sequences of two continuous circular arcs. The algorithm runs in O(n) time and embeds the graph on the O(n)\times O(n) grid, while maintaining Θ(1/d(v)) angular resolution, where d(v) is the degree of vertex v . Since in this case we use circular arcs of infinite radius, this is also the first algorithm that simultaneously achieves good angular resolution, small area, and at most one bend per edge using straight-line segments. Finally, we show how to create drawings in which edges are smooth C ¹ -continuous curves, represented by a sequence of at most three circular arcs. Received September 30, 1999, and in revised form March 27, 2000. Online publication October 26, 2000.     

Halving circular arcs in normed planes

Studying the relation between the length of a chord of the unit circle and the length of the arc corresponding to it, some new characterizations of the Euclidean plane among all normed planes are obtained. All these results yield characterizations of inner product spaces in higher dimensions. Supported by the National Natural Science Foundation of China, grant number 10671048.     

Approximation of circular arcs by parametric polynomial curves

In this paper the approximation of circular arcs by parametric polynomial curves is studied. If the angular length of the circular arc is h, a parametric polynomial curve of arbitrary degree \(n \in {\mathbb{N}}\) , which interpolates given arc at a particular point, can be constructed with radial distance bounded by h ²ⁿ . This is a generalization of the result obtained by Lyche and Mørken for odd n.     

A theorem on graph embedding with a relation to hyperbolic volume

We prove that a planar cubic cyclically 4-connected graph of odd χ < 0 is the dual of a 1-vertex triangulation of a closed orientable surface. We explain how this result is related to (and applied to prove at a separate place) a theorem about hyperbolic volume of links: the maximal volume of alternating links of given χ < 0 does not depend on the number of their components.     

On embedding a cycle in a plane graph

Consider a planar drawing Γ of a planar graph G such that the vertices are drawn as small circles and the edges are drawn as thin stripes. Consider a non-simple cycle c of G. Is it possible to draw c as a non-intersecting closed curve inside Γ, following the circles that correspond in Γ to the vertices of c and the stripes that connect them? We show that this test can be done in polynomial time and study this problem in the framework of clustered planarity for highly non-connected clustered graphs.     

Capacity of a condenser whose plates are circular arcs

We find an asymptotic formula for the conformal capacity of a plane condenser both plates of which are concentric circular arcs as the distance between them vanishes. This result generalizes the formula for the capacity of parallel linear plate condenser found by Simonenko and Chekulaeva (1972). On a capacity of a condenser consisting of infinite bands, Izv. Vyssh. Uchebn. Zaved. Elektromekh., 4, 362–370 (in Russian) and sheds light on the problem of finding an asymptotic formula for the capacity of condenser whose plates are arbitrary parallel curves. This problem was posed and partially solved by R. Kühnau (1998). Randeffekten beim elektostatischen Kondensator, Zap. Nauchn. Semin. POMI, 254, 132–154.     

The circular dimension of a graph

A graph is a pair (V, I), V being the vertices and I being the relation of adjacency on V. Given a graph G, then a collection of functions {f_i}^m_n=1, each f_i mapping each vertex of V into anarc on a fixed circle, is said to define an m-arc intersection model for G if for all x,y ? V, xly ? (∨_i?m)(f_i(x)∩f_i(y)≠Ø). The circular dimension of a graph G is defined as the smallest integer m such that G has an m-arc intersection model. In this paper we establish that the maximum circular dimension of any complete partite graph having n vertices is the largest integer p such that 2^p+p?n+1.     

Approximation of an open polygonal curve with a minimum number of circular arcs and biarcs

We present an algorithm for approximating a given open polygonal curve with a minimum number of circular arcs. In computer-aided manufacturing environments, the paths of cutting tools are usually described with circular arcs and straight line segments. Greedy algorithms for approximating a polygonal curve with curves of higher order can be found in the literature. Without theoretical bounds it is difficult to say anything about the quality of these algorithms. We present an algorithm which finds a series of circular arcs that approximate the polygonal curve while remaining within a given tolerance region. This series contains the minimum number of arcs of any such series. Our algorithm takes O(n²logn) time for an original polygonal chain with n vertices. Using a similar approach, we design an algorithm with a runtime of O(n²logn), for computing a tangent-continuous approximation with the minimum number of biarcs, for a sequence of points with given tangent directions.     

Crossing numbers of graph embedding pairs on closed surfaces

We shall prove that any two graphs G₁ and G₂ can be embedded together on a closed surface of genus g with at most 4g · β(G₁) · β(G₂) crossing points on their edges if they are embeddable on the surface, where β(G) stands for the Betti number of G, and show several observations on crossings of graph embedding pairs. © 2000 John Wiley & Sons, Inc. J Graph Theory 36: 8–23, 2001     

On embedding an outer-planar graph in a point set

Given an n-vertex outer-planar graph G and a set P of n points in the plane, we present an O(nlog³n) time and O(n) space algorithm to compute a straight-line embedding of G in P, improving upon the algorithm in [8,12] that requires O(n²) time. Our algorithm is near-optimal as there is an Ω(nlogn) lower bound for the problem [4]. We present a simpler O(nd) time and O(n) space algorithm to compute a straight-line embedding of G in P where lognd2n is the length of the longest vertex disjoint path in the dual of G. Therefore, the time complexity of the simpler algorithm varies between O(nlogn) and O(n²) depending on the value of d. More efficient algorithms are presented for certain restricted cases. If the dual of G is a path, then an optimal Θ(nlogn) time algorithm is presented. If the given point set is in convex position then we show that O(n) time suffices.     

A relative maximum genus graph embedding and its local maximum genus

A relative embedding of a connected graph is an embedding of the graph in some surface with respect to some closed walks, each of which bounds a face of the embedding. The relative maximum genus of a connected graph is the maximum of integerk with the property that the graph has a relative embedding in the orientable surface withk handles. A polynomial algorithm is provided for constructing relative maximum genus embedding of a graph if the relative tree of the graph is planar. Under this condition, just like maximum genus embedding, a graph does not have any locally strict maximum genus.     

On the length preserving approximation of plane curves by circular arcs

A technique for the length preserving approximation of plane curves by two circular arcs is analyzed. The conditions under which this technique can be applied are extended, and certain consequences of the proved results unrelated to the approximation problem are discussed. More precisely, inequalities for the length of a convex spiral arc subject to the given boundary conditions are obtained. Conjectures on curve closeness conditions obtained using computer simulation are discussed.     

On circular–linear one-factorizations of the complete graph

In Korchmáros et al. (2018)one-factorizations of the complete graph $K_n$ are constructed for $n=q+1$ with any odd prime power $q$ such that either $q\equiv 1(mod4)$ or $q=2^h?1$. The arithmetic restriction $n=q+1$ is due to the fact that the vertices of $K_n$ in the construction are the points of a conic $\Omega$ in the finite plane of order $q$. Here we work on the Euclidean plane and describe an analogous construction where the role of $\Omega$ is taken by a regular $n$-gon. This allows us to remove the above constraints and construct one-factorizations of $K_n$ for every even $n\ge 6$.     

Feature extraction using two-dimensional local graph embedding based on maximum margin criterion

In this paper, we propose a novel method for image feature extraction, namely the two-dimensional local graph embedding, which is based on maximum margin criterion and thus not necessary to convert the image matrix into high-dimensional image vector and directly avoid computing the inverse matrix in the discriminant criterion. This method directly learns the optimal projective vectors from 2D image matrices by simultaneously considering local graph embedding and maximum margin criterion. The proposed method avoids huge feature matrix problem in Eigenfaces, Fisherfaces, Laplacianfaces, maximum margin criterion (MMC) and inverse matrix in 2D Fisherfaces, 2D Laplacianfaces and 2D Local Graph Embedding Discriminant Analysis (2DLGEDA) so that computational time would be saved for feature extraction. Experimental results on the Yale and the USPS databases show the effectiveness of the proposed method under various experimental conditions.