2
$\begingroup$

Given a multigraph embedded in the plane call a maximal set of parallel edges between $u,v$ such that only one of the induced faces contains nodes besides $u$ or $v$ a topologically parallel set (tell me if there is standard terminology for this).

Given a topologically parallel set $S$ of edges between $u$ and $v$ we say that an edge $e$ dipsinto the set $S$ if $e$ intersects some but not all edges of $S$.

Is it true that Given a multigraph $G$ with an embedding $\phi$, there is an embedding $\phi'$ with $\phi(V) = \phi'(V)$, preserving the topologically parallel sets such that no edge $e$ dips into a topologically parallel set. Further if two edges cross in $\phi'$, then they cross in $\phi$.

I'm fairly sure this is true simply perturb the drawing so that edges no longer dip into topologcially parallel sets. Transformation of <span class=$\phi$ into $\phi'$" />

I also posted this here https://math.stackexchange.com/questions/4937351/dipping-into-sets-of-parallel-edges-in-graph-drawings

$\endgroup$
1
  • 1
    $\begingroup$ There is a standard terminology: Homotopic parallel edges are defined to not have any vertices in the bounded components they leave after removing the closed curve obtained by concatenating them. If you are on the sphere instead of the plane you would say that one component contains all vertices. So what you describe are pairwise homotopic parallel edges. $\endgroup$ Commented Jul 31 at 15:49

1 Answer 1

3
$\begingroup$

The following should work: for $uv$ with parallel edges connecting them, consider the union of faces not containing vertices, blow it up slightly if necessary to make it disk-shaped and let $\alpha$, $\beta$ be the two $uv$-arcs bounding that disk. Any edge that intersects $\alpha$ and $\beta$ consecutively must intersect all edges between $u$ and $v$. So such an edge can't dip into the edges connecting them. Therefore any such edge which enters the disk must leave the disk via the same arc. You can then shortcut such an edge by following that arc outside the disk. This needs to be done starting with a smallest such arc (in terms of enclosed region inside the disk). Then any new intersections must be with edges it already intersected inside the disk.

$\endgroup$

You must log in to answer this question.

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