10
$\begingroup$

I consider embeddings of graphs into 3-space with edges embedded as arbitrary curves. In the simplest (non-trivial) case the graph $G$ is a cycle or union of cycles, in which case the embeddings can already be very complicated, forming knots and links. Still, it is uncontroversial what is the simplest embedding: the unknot or unlink.

For general graphs $G$ this seems less clear. For example, if $G=K_6$ then every embedding has two linked cycles; and if $G=K_7$ then every embedding has a knotted cycle. So we cannot avoid links and knots in general.

Question: How to define a sensible notion of "simplest" (least knotted, least linked, ...) embedding for a given graph $G$? Is there a notion of complexity for graph embeddings in the literature?

Note that the "simplest" embedding might not be unique. Instead I am looking for a way to decide (or meaningfully define) what it means for an embedding to "have no more knots/links than absolutely necessary". Perhaps one could just count knotted cycles and tuples of linked cycles and try to minimize this number. But it is not clear to me how to weigh knots against links, and links against larger links or more complicated links, etc. My primary hope is that there is a canonical "simplest" embedding (or family of embeddings), that are uncontroversially "simplest", just like the unknot and unlink.

Improve this question
$\endgroup$
8
  • $\begingroup$ My immediate thought is that there is no hope of a single "best" notion of "simplest embedding". As an example of the problems that arise, consider the idea of an "intrinsically knotted graph". $\endgroup$
    – Sam Nead
    Commented Aug 16 at 14:04
  • 1
    $\begingroup$ Achieving the minimum crossing number, over all embeddings and all orthogonal projections to a plane, might be a start. $\endgroup$
    – Daniel Asimov
    Commented Aug 16 at 16:01
  • 2
    $\begingroup$ Something close to Daniel's suggestion would be to put a uniform electrostatic charge on your graph (thought of as like a rubber material) and minimize the electrostatic potential on all embeddings, much like we do for knots. In the knot situation this is known to be closely related to crossing number. $\endgroup$
    – Ryan Budney
    Commented Aug 16 at 17:05
  • 1
    $\begingroup$ Or you could embed into the three-sphere and minimise the number of tetrahedra needed to triangulate the complement of the graph. Or you could (for a trivalent graph) decorate the graph with three's and treat the embedded graph as a orbifold locus and try to minimise the hyperbolic volume. Or you could give all of the edges length one, and try to minimise the metric distortion of the embedding... What "best" means depends on what you want. And you have not told us that. (Beyond suggesting that you care a more about topology than you do about geometry.) $\endgroup$
    – Sam Nead
    Commented Aug 16 at 17:32
  • 1
    $\begingroup$ The technique for the graphs displayed in commons.wikimedia.org/wiki/… is to define the usual graph-theoretic distances between vertices, to define the Euclidean distance of their representation in 3D space, and to minimize the sum of the squared differences between these two distances. This usually gives structures that represent symmetries well. $\endgroup$
    – R. J. Mathar
    Commented Aug 17 at 11:28

2 Answers 2

Reset to default
5
$\begingroup$

Another way to generate a topologically simple embedding into $\mathbb{R}^3$ is to embed the graph in a surface of minimal genus which in turn embeds into $\mathbb{R}^3$. One can generate the different embeddings in surfaces by choosing a cyclical ordering of the adjacent edges at every vertex and use that ordering to glue in unit disks to create the surface. I'm not sure how these embeddings relate to the number of links and knots.

Improve this answer
$\endgroup$
3
  • $\begingroup$ This is a very nice idea! $\endgroup$
    – M. Winter
    Commented Aug 17 at 18:51
  • $\begingroup$ I accepted this answer because it works for all graphs and because it is a nice idea for capturing the topological simplicity (as opposed to geometric simplicity) that I had in mind. $\endgroup$
    – M. Winter
    Commented Aug 20 at 12:04
  • $\begingroup$ I just realized the following: $K_7$ has genus 1, so embeds in a torus. It is also intrinsically knotted, so one of its Hamiltonian cycles is knotted. Remove an edge from $K_7$ that is not in this Hamiltonian cycle. The graph still has genus 1, so the previous embedding is "best possible" in terms of genus. But it is not knotless. This is just a comment to show that lowest genus embeddings do not necessarily yield linkless/knotless in all cases where it is possible. $\endgroup$
    – M. Winter
    Commented Aug 21 at 12:12
7
$\begingroup$

I agree with the comments that there will be no simplest embedding in general. Nevertheless in certain cases there are embeddings with nicer properties.

One way to embed a simplicial graph (ie no loops or multi-edges) is to put the vertices on the twisted cubic $(x,x^2,x^3)$. This requires choosing an ordering on the vertices, and isn’t guaranteed to be simplest in a topological sense.

Another way to get a “simpler” embedding of any (finite) graph is to choose an embedding so that the complement is a handlebody (so take the graph as the core of one handlebody of a Heegaard splitting of $S^3$; all such Heegaard splittings are isotopic). But a complicated embedding of the graph into a handlebody will make a complicated embedding into $S^3$.

For certain graphs that have a linkless embedding (such as $K_{3,3}, K_5$), in fact they have an embedding that is “paneled ”, meaning that every closed curve in the graph bounds a disk disjoint from the graph. For example planar graphs have such embeddings when they embed in the plane in 3-space. It turns out that planar graphs have a unique planar embeding up to isotopy, but I’m not sure about flat embeddings of graphs in general.

Another notion of simplest embedding (akin to minimizing crossing number) is to choose one minimizing the book thickness. Unfortunately this doesn’t tell one anything about knotted cycles since any knot embeds in a 3-page book.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Thanks Ian for your answer! Let me add to the fourth paragraph: $K_5$ and $K_{3,3}$ have exactly two non-equivalent flat/paneled embeddings. So every flat graph has a finite number of such embeddings, all of which I would consider equally "simplest". $\endgroup$
    – M. Winter
    Commented Aug 17 at 18:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .