### Wednesday, January 23rd, 2019, 16:10

### Schreiber 309

### Weak Embeddings and Crossing Minimization

### Csaba D. Toth, CSUN

### Abstract:

An *embedding* $\varphi:G\rightarrow M$ of a graph $G$ into a 2-manifold $M$ maps the vertices in $V(G)$ to distinct points and the

edges in $E(G)$ to interior-disjoint Jordan arcs between the corresponding vertices. Due to data compression or low resolution,

nearby vertices and edges of a graph drawing may be bundled to a common node or arc. This raises the computational problem of deciding whether a

given map $\varphi:G\rightarrow M$ corresponds comes from an embedding.

A map $\varphi:G\rightarrow M$ is a *weak embedding* if it can be perturbed into an embedding $\psi_\varepsilon:G\rightarrow M$ with

$\|\varphi-\psi_\varepsilon\|<\varepsilon$ for every $\varepsilon>0$.

We present an $O(n\log n)$-time algorithm that recognizes weak embeddings: It performs a sequence of local operations that gradually

"untangles" the image $\varphi(G)$ into an embedding $\psi(G)$, or reports that $\varphi$ is not a weak embedding. Similar local operations

can also be used for perturbing a given map $\varphi:G\rightarrow M$ into a proper drawing that minimizes the number of crossings when $G$ is

a cycle and the map $\varphi$ has no *spurs* (i.e., no two adjacent edges are mapped to overlapping arcs). However, crossing

minimization is NP-complete (i) when $G$ is an arbitrary graph and $\varphi$ has no spurs, and (ii) when $\varphi$ may have spurs and $G$

is a cycle or a union of disjoint paths.

Joint work with Hugo Akitaya and Radoslav Fulek