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 3-tree 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) k-Lombardi drawings, in which each edge may be drawn as a (differentiable)
sequence of k circular arcs; we show that every graph has a smooth 2-Lombardi drawing
and every planar graph has a smooth planar 3-Lombardi 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 3-dimensional simple closed curves into lR2, such that no more than two points project to the same point in lR2. These diagrams are drawings of 4-regular 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 circular-arc edges and perfect angular resolution). We show that several knots do not allow crossing-minimal plane Lombardi drawings. On the other hand, we identify a large class of 4-regular plane multigraphs that do have plane Lombardi drawings. We then study two relaxations of Lombardi drawings and show that every knot admits a crossing-minimal plane 2-Lombardi drawing (where edges are composed of two circular arcs). Further, every knot is near-Lombardi, 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
- NSF-PAR ID:
- 10179544
- Date Published:
- Journal Name:
- Journal of computational geometry
- Volume:
- 10
- Issue:
- 1
- ISSN:
- 1920-180X
- Page Range / eLocation ID:
- 444-476
- 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, k-planar graphs are those graphs that can be drawn so that every edge has at most k crossings (i.e., they admit a k-plane drawing). It is known that for k≤3 , every k-planar graph admits a k-plane simple drawing. But for k≥4 , there exist k-planar graphs that do not admit a k-plane simple drawing. Answering a question by Schaefer, we show that there exists a function Open image in new window such that every k-planar 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 4-planar graph admits an 8-plane 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 non-adequate prime satellite knots. More specifically, we exhibit minimal crossing number diagrams for untwisted Whitehead doubles of zero-writhe 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 zero-writhe adequate knot.more » « less
-
We consider the classical Minimum Crossing Number problem: given an n-vertex 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 APX-hardness, 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
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1007/978-3-319-73915-1_10
