##### Personal tools
You are here: Home 2019 Weak Embeddings and Crossing Minimization
« August 2019 »
August
SuMoTuWeThFrSa
123
45678910
11121314151617
18192021222324
25262728293031

# Weak Embeddings and Crossing Minimization

### 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