In Lombardi drawings of graphs, edges are represented as circular arcs and the
edges incident on vertices have perfect angular resolution. It is known that not every planar
graph has a planar Lombardi drawing. We give an example of a planar 3tree that has
no planar Lombardi drawing and we show that all outerpaths do have a planar Lombardi
drawing. Further, we show that there are graphs that do not even have any Lombardi
drawing at all. With this in mind, we generalize the notion of Lombardi drawings to that
of (smooth) kLombardi drawings, in which each edge may be drawn as a (differentiable)
sequence of k circular arcs; we show that every graph has a smooth 2Lombardi drawing
and every planar graph has a smooth planar 3Lombardi drawing. We further investigate
related topics connecting planarity and Lombardi drawings.
more »
« less
Lombardi drawings of knots and links
Knot and link diagrams are projections of one or more 3dimensional simple closed curves into lR2, such that no more than two points project to the same point in lR2. These diagrams are drawings of 4regular plane multigraphs. Knots are typically smooth curves in lR3, so their projections should be smooth curves in lR2 with good continuity and large crossing angles: exactly the properties of Lombardi graph drawings (defned by circulararc edges and perfect angular resolution). We show that several knots do not allow crossingminimal plane Lombardi drawings. On the other hand, we identify a large class of 4regular plane multigraphs that do have plane Lombardi drawings. We then study two relaxations of Lombardi drawings and show that every knot admits a crossingminimal plane 2Lombardi drawing (where edges are composed of two circular arcs). Further, every knot is nearLombardi, that is, it can be drawn as a plane Lombardi drawing when relaxing the angular resolution requirement by an arbitrary small angular offset ε, while maintaining a 180◦ angle between opposite edges.
more »
« less
 Award ID(s):
 1712119
 NSFPAR ID:
 10179544
 Date Published:
 Journal Name:
 Journal of computational geometry
 Volume:
 10
 Issue:
 1
 ISSN:
 1920180X
 Page Range / eLocation ID:
 444476
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


null (Ed.)Every finite graph admits a simple (topological) drawing, that is, a drawing where every pair of edges intersects in at most one point. However, in combination with other restrictions simple drawings do not universally exist. For instance, kplanar graphs are those graphs that can be drawn so that every edge has at most k crossings (i.e., they admit a kplane drawing). It is known that for k≤3 , every kplanar graph admits a kplane simple drawing. But for k≥4 , there exist kplanar graphs that do not admit a kplane simple drawing. Answering a question by Schaefer, we show that there exists a function Open image in new window such that every kplanar graph admits an f(k)plane simple drawing, for all Open image in new window. Note that the function f depends on k only and is independent of the size of the graph. Furthermore, we develop an algorithm to show that every 4planar graph admits an 8plane simple drawing.more » « less

It has long been known that the quadratic term in the degree of the colored Jones polynomial of a knot is bounded above in terms of the crossing number of the knot. We show that this bound is sharp if and only if the knot is adequate. As an application of our result we determine the crossing numbers of broad families of nonadequate prime satellite knots. More specifically, we exhibit minimal crossing number diagrams for untwisted Whitehead doubles of zerowrithe adequate knots. This allows us to determine the crossing number of untwisted Whitehead doubles of any amphicheiral adequate knot, including, for instance, the Whitehead doubles of the connected sum of any alternating knot with its mirror image. We also determine the crossing number of the connected sum of any adequate knot with an untwisted Whitehead double of a zerowrithe adequate knot.more » « less

We consider the classical Minimum Crossing Number problem: given an nvertex graph G, compute a drawing of G in the plane, while minimizing the number of crossings between the images of its edges. This is a fundamental and extensively studied problem, whose approximability status is widely open. In all currently known approximation algorithms, the approximation factor depends polynomially on Δ – the maximum vertex degree in G. The best current approximation algorithm achieves an O(n1/2−· (Δ·logn))approximation, for a small fixed constant є, while the best negative result is APXhardness, leaving a large gap in our understanding of this basic problem. In this paper we design a randomized O(2O((logn)7/8loglogn)·(Δ))approximation algorithm for Minimum Crossing Number. This is the first approximation algorithm for the problem that achieves a subpolynomial in n approximation factor (albeit only in graphs whose maximum vertex degree is subpolynomial in n). In order to achieve this approximation factor, we design a new algorithm for a closely related problem called Crossing Number with Rotation System, in which, for every vertex v∈ V(G), the circular ordering, in which the images of the edges incident to v must enter the image of v in the drawing is fixed as part of input. Combining this result with the recent reduction of [Chuzhoy, Mahabadi, Tan ’20] immediately yields the improved approximation algorithm for Minimum Crossing Number.more » « less

The representation of knots by petal diagrams (Adams et al 2012) naturally defines a sequence of distributions on the set of knots. We establish some basic properties of this randomized knot model. We prove that in the random n–petal model the probability of obtaining every specific knot type decays to zero as n, the number of petals, grows. In addition we improve the bounds relating the crossing number and the petal number of a knot. This implies that the n–petal model represents at least exponentially many distinct knots. Past approaches to showing, in some random models, that individual knot types occur with vanishing probability rely on the prevalence of localized connect summands as the complexity of the knot increases. However, this phenomenon is not clear in other models, including petal diagrams, random grid diagrams and uniform random polygons. Thus we provide a new approach to investigate this question.more » « less