ﻻ يوجد ملخص باللغة العربية
We study $k$-page upward book embeddings ($k$UBEs) of $st$-graphs, that is, book embeddings of single-source single-sink directed acyclic graphs on $k$ pages with the additional requirement that the vertices of the graph appear in a topological ordering along the spine of the book. We show that testing whether a graph admits a $k$UBE is NP-complete for $kgeq 3$. A hardness result for this problem was previously known only for $k = 6$ [Heath and Pemmaraju, 1999]. Motivated by this negative result, we focus our attention on $k=2$. On the algorithmic side, we present polynomial-time algorithms for testing the existence of $2$UBEs of planar $st$-graphs with branchwidth $beta$ and of plane $st$-graphs whose faces have a special structure. These algorithms run in $O(f(beta)cdot n+n^3)$ time and $O(n)$ time, respectively, where $f$ is a singly-exponential function on $beta$. Moreover, on the combinatorial side, we present two notable families of plane $st$-graphs that always admit an embedding-preserving $2$UBE.
We analyze a directed variation of the book embedding problem when the page partition is prespecified and the nodes on the spine must be in topological order (upward book embedding). Given a directed acyclic graph and a partition of its edges into $k
Let $S$ be a set of $n$ sites, each associated with a point in $mathbb{R}^2$ and a radius $r_s$ and let $mathcal{D}(S)$ be the disk graph on $S$. We consider the problem of designing data structures that maintain the connectivity structure of $mathca
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 result
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
Let $Vsubsetmathbb{R}^2$ be a set of $n$ sites in the plane. The unit disk graph $DG(V)$ of $V$ is the graph with vertex set $V$ in which two sites $v$ and $w$ are adjacent if and only if their Euclidean distance is at most $1$. We develop a compact