Titlebook: ;

经典

https://doi.org/10.1007/978-1-4612-0555-5We present time-efficient algorithms for encoding (and decoding) planar orthogonal drawings of degree-4 and degree-3 biconnected and triconnected planar graphs using small number of bits. We also present time-efficient algorithms for encoding (and decoding) turn-monotone planar orthogonal drawing.

GEM

横截,横断

Drawing Outer-Planar Graphs in ,(, log , )AreaIn this paper,we study drawings of outer-planar graphs in various models.We showthat . (. log . )area can be achieved for such drawings if edges are allowed to have bends or if vertices may be represented by boxes.The question of straight-line grid-drawings of outer- planar graphs in o (.. )area remains open.

要求比…更好

An Efficient Fixed Parameter Tractable Algorithm for 1-Sided Crossing MinimizationWe give an .(ø. · ..) algorithm for the 1-. problem, thus showing that the problem is Fixed Parameter Tractable. The constant ø in the running time is the golden ratio .. The constant . is the parameter of the problem: the number of alloweded ge crossings.

Mortar

Separating Thickness from Geometric ThicknessWe show that graph-theoretic thickness and geometric thickness are not asymptotically equivalent: for every ., there exists a graph with thickness three and geometric thickness ≥ ..

Seminar