ﻻ يوجد ملخص باللغة العربية
Partial edge drawing (PED) is a drawing style for non-planar graphs, in which edges are drawn only partially as pairs of opposing stubs on the respective end-vertices. In a PED, by erasing the central parts of edges, all edge crossings and the resulting visual clutter are hidden in the undrawn parts of the edges. In symmetric partial edge drawings (SPEDs), the two stubs of each edge are required to have the same length. It is known that maximizing the ink (or the total stub length) when transforming a straight-line graph drawing with crossings into a SPED is tractable for 2-plane input drawings, but NP-hard for unrestricted inputs. We show that the problem remains NP-hard even for 3-plane input drawings and establish NP-hardness of ink maximization for PEDs of 4-plane graphs. Yet, for k-plane input drawings whose edge intersection graph forms a collection of trees or, more generally, whose intersection graph has bounded treewidth, we present efficient algorithms for computing maximum-ink PEDs and SPEDs. We implemented the treewidth-based algorithms and show a brief experimental evaluation.
When can a plane graph with prescribed edge lengths and prescribed angles (from among ${0,180^circ, 360^circ$}) be folded flat to lie in an infinitesimally thin line, without crossings? This problem generalizes the classic theory of single-vertex fla
K{a}rolyi, Pach, and T{o}th proved that every 2-edge-colored straight-line drawing of the complete graph contains a monochromatic plane spanning tree. It is open if this statement generalizes to other classes of drawings, specifically, to simple draw
Symmetry is an important factor in human perception in general, as well as in the visualization of graphs in particular. There are three main types of symmetry: reflective, translational, and rotational. We report the results of a human subjects expe
We study the question whether a crossing-free 3D morph between two straight-line drawings of an $n$-vertex tree can be constructed consisting of a small number of linear morphing steps. We look both at the case in which the two given drawings are two
Hills Conjecture states that the crossing number $text{cr}(K_n)$ of the complete graph $K_n$ in the plane (equivalently, the sphere) is $frac{1}{4}lfloorfrac{n}{2}rfloorlfloorfrac{n-1}{2}rfloorlfloorfrac{n-2}{2}rfloorlfloorfrac{n-3}{2}rfloor=n^4/64 +