Personal tools
You are here: Home CG seminar 2019 Weak Embeddings and Crossing Minimization
« February 2019 »
Log in

Forgot your password?

Weak Embeddings and Crossing Minimization

Wednesday, January 23rd, 2019, 16:10

Schreiber 309


Weak Embeddings and Crossing Minimization

Csaba D. Toth, CSUN


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
Document Actions